1 Préparatifs

setwd("~/GitHub/Cours_2020_UniGE/Cours_Geneve_8")
#je charge les données que l'enseignant a préparé pour éviter les problèmes
#load("Cours_Geneve_8.RData")
if(!require("devtools")){
  install.packages("devtools")
  library(devtools)
}
if(!require("igraph")){
  install.packages("igraph")
  library(igraph)
}
if(!require("tidyverse")){
  install.packages("tidyverse")
  library(tidyverse)
}
if(!require("tidygraph")){
  install.packages("tidygraph")
  library(tidygraph)
}
if(!require("ggraph")){
  install.packages("ggraph")
  library(ggraph)
}
if(!require("qgraph")){
  install.packages("qgraph")
  library(qgraph)
}
if(!require("corrr")){
  install.packages("corrr")
  library(corrr)
}
if(!require("visNetwork")){
  install.packages("visNetwork")
  library(visNetwork)
}
if(!require("networkD3")){
  install.packages("networkD3")
  library(networkD3)
}
if(!require("ForceAtlas2")){
  devtools::install_github("analyxcompany/ForceAtlas2")
  library(ForceAtlas2)
}
if(!require("rgl")){
  install.packages("rgl")
  library(rgl)
}
if(!require("igraphdata")){
  install.packages("igraphdata")
  library(igraphdata)
}
if(!require("netrankr")){
  install.packages("netrankr")
  library(netrankr)
}
if(!require("popgraph")){
  devtools::install_github("dyerlab/popgraph")
  library(popgraph)
}
if(!require("ggmap")){
  install.packages("ggmap")
  library(ggmap)
}

Je charge mes deux fichiers: celui avec les nœuds (nodes.csv) et celui avec les arêtes (edges.csv).

nodes <- as.data.frame(read.csv(file="data/basic/nodes.csv", sep = "\t", header = FALSE))
edges <- as.data.frame(read.csv(file="data/basic/edges.csv", sep = "\t", header = FALSE))
#Je donne un nom aux colonnes de chaque data.frame
colnames(nodes) <- c("id", "label","type")
colnames(edges) <- c("from", "to")
#Je contrôle que tout est en ordre

J’affiche les premiers éléments de chaque fichier, et je compte les rangs pour me faire une idée de ce qui se trouve dans mes données

head(nodes)
  id              label      type
1  1            Molière    Auteur
2  2 Guillaume de Luyne  Libraire
3  3      Claude Barbin  Libraire
4  4   Charles de Sercy  Libraire
5  5       Jean Hénault Imprimeur
6  6      François Noël Imprimeur
head(edges)
  from to
1    1  2
2    1  3
3    1  4
4    1  5
5    1  6
6    1  7
nrow(nodes); length(unique(nodes$id))
[1] 27
[1] 27
nrow(edges); nrow(unique(edges[,c("from", "to")]))
[1] 242
[1] 106

Je transforme ces deux objets en données igraph, qui vont me permettre de faire mes analyses de réseau par la suite.

data <- graph_from_data_frame(d=edges, vertices=nodes, directed=F) 
class(data)
[1] "igraph"

Mes données se présentent sous cette forme:

data
IGRAPH a34656a UN-B 27 242 -- 
+ attr: name (v/c), label (v/c), type (v/c)
+ edges from a34656a (vertex names):
 [1] 1 --2  1 --3  1 --4  1 --5  1 --6  1 --7  2 --3  2 --4  2 --5  2 --6  2 --7  3 --4 
[13] 3 --5  3 --6  3 --7  4 --5  4 --6  4 --7  5 --6  5 --7  6 --7  1 --8  1 --9  1 --7 
[25] 8 --9  7 --8  7 --9  1 --4  1 --2  1 --10 1 --3  1 --12 1 --7  2 --4  4 --10 3 --4 
[37] 4 --12 4 --7  2 --10 2 --3  2 --12 2 --7  3 --10 10--12 7 --10 3 --12 3 --7  7 --12
[49] 1 --2  1 --4  1 --10 1 --3  1 --12 1 --7  2 --4  2 --10 2 --3  2 --12 2 --7  4 --10
[61] 3 --4  4 --12 4 --7  3 --10 10--12 7 --10 3 --12 3 --7  7 --12 1 --3  1 --12 1 --7 
[73] 3 --12 3 --7  7 --12 1 --3  1 --12 1 --13 3 --12 3 --13 12--13 1 --2  1 --4  1 --14
[85] 1 --15 1 --16 1 --10 1 --3  1 --12 1 --5  2 --4  2 --14 2 --15 2 --16 2 --10 2 --3 
+ ... omitted several edges

Je peux désormais afficher les nœuds, les arêtes de cette manière. Je peux aussi sélectionner certaines colonnes pour chaque fichier d’une manière particulière aux objets igraph

#edges
E(data)
+ 242/242 edges from a34656a (vertex names):
  [1] 1 --2  1 --3  1 --4  1 --5  1 --6  1 --7  2 --3  2 --4  2 --5  2 --6  2 --7  3 --4 
 [13] 3 --5  3 --6  3 --7  4 --5  4 --6  4 --7  5 --6  5 --7  6 --7  1 --8  1 --9  1 --7 
 [25] 8 --9  7 --8  7 --9  1 --4  1 --2  1 --10 1 --3  1 --12 1 --7  2 --4  4 --10 3 --4 
 [37] 4 --12 4 --7  2 --10 2 --3  2 --12 2 --7  3 --10 10--12 7 --10 3 --12 3 --7  7 --12
 [49] 1 --2  1 --4  1 --10 1 --3  1 --12 1 --7  2 --4  2 --10 2 --3  2 --12 2 --7  4 --10
 [61] 3 --4  4 --12 4 --7  3 --10 10--12 7 --10 3 --12 3 --7  7 --12 1 --3  1 --12 1 --7 
 [73] 3 --12 3 --7  7 --12 1 --3  1 --12 1 --13 3 --12 3 --13 12--13 1 --2  1 --4  1 --14
 [85] 1 --15 1 --16 1 --10 1 --3  1 --12 1 --5  2 --4  2 --14 2 --15 2 --16 2 --10 2 --3 
 [97] 2 --12 2 --5  4 --14 4 --15 4 --16 4 --10 3 --4  4 --12 4 --5  14--15 14--16 10--14
[109] 3 --14 12--14 5 --14 15--16 10--15 3 --15 12--15 5 --15 10--16 3 --16 12--16 5 --16
+ ... omitted several edges
#nodes
V(data)
+ 27/27 vertices, named, from a34656a:
 [1] 1  2  3  4  5  6  7  8  9  10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
#nodes labels
V(data)$label
 [1] "Molière"                  "Guillaume de Luyne"       "Claude Barbin"           
 [4] "Charles de Sercy"         "Jean Hénault"             "François Noël"           
 [7] "Christophe Journel"       "Sieur de Neuf-Villenaine" "Jean Ribou"              
[10] "Jean Guignard"            "Gabriel Quinet"           "François II Noël"        
[13] "Thomas Jolly"             "Louis Billaine"           "Estienne Loyson"         
[16] "Claude Blageart"          "Pierre Trabouillet"       "Nicolas Le Gras"         
[19] "Théodore Girard"          "Etienne Maucroy"          "Claude II Calleville"    
[22] "Claude Audinet"           "Pierre Le Monnier"        "Pierre Corneille"        
[25] "Philippe Quinault"        "Pierre Promé"             "François Muguet"         
#nodes types
V(data)$type
 [1] "Auteur"    "Libraire"  "Libraire"  "Libraire"  "Imprimeur" "Imprimeur" "Imprimeur"
 [8] "Libraire"  "Libraire"  "Libraire"  "Libraire"  "Imprimeur" "Libraire"  "Libraire" 
[15] "Libraire"  "Imprimeur" "Libraire"  "Libraire"  "Libraire"  "Imprimeur" "Imprimeur"
[22] "Imprimeur" "Libraire"  "Auteur"    "Auteur"    "Libraire"  "Imprimeur"

2 Mon premier graphe

Je peux désormais fabriquer mon réseau avec la fonction plot:

plot(data) 

Il existe une fonction alternative plot.igraph, qui fait la même chose

plot.igraph(data) 

Il existe enfin une fonction tkplot qui est un prototype d’interface utilisateur:

#tkplot(data)

Je dispose d’un grand nombre de paramètres pour modifier l’apparence de mon graph et le rendre (si on en a le talent) esthétique:

plot(data,
     #courbure de l'arête
     edge.curved=0.1,
     #couleur de l'arête
     edge.color="orange",
     #couleur du nœud
     vertex.color="green",
     #couleur du contour du nœud
     vertex.frame.color="#555555",
     #couleur de l'étiquette du nœud
     vertex.label.color="darkred",
     #contenu de l'étiquette du nœud
     vertex.label=V(data)$type,
     #taille de la police
     vertex.label.cex=1) 

On peut customiser encore plus la décoration en intervenant plus lourdement sur la mise en page. Une manière de faire va être de créer des vecteurs à partir des données, en substituant la valeur qui nous intéresse par la forme que l’on souhaite lui donner. Par exemple, si je veux changer la couleur du nœud en fonction du label

#J'ai une colonne de mon objet igraph avec les labels
V(data)$type
 [1] "Auteur"    "Libraire"  "Libraire"  "Libraire"  "Imprimeur" "Imprimeur" "Imprimeur"
 [8] "Libraire"  "Libraire"  "Libraire"  "Libraire"  "Imprimeur" "Libraire"  "Libraire" 
[15] "Libraire"  "Imprimeur" "Libraire"  "Libraire"  "Libraire"  "Imprimeur" "Imprimeur"
[22] "Imprimeur" "Libraire"  "Auteur"    "Auteur"    "Libraire"  "Imprimeur"
#je copie le contenu de cette colonne dans un nouvel objet
to_colors<-V(data)$type
#Je substitue toute les cellules avec l'information `libraire` par la couleur souhaitée
to_colors<-replace(to_colors,to_colors=="Libraire","orange")
to_colors
 [1] "Auteur"    "orange"    "orange"    "orange"    "Imprimeur" "Imprimeur" "Imprimeur"
 [8] "orange"    "orange"    "orange"    "orange"    "Imprimeur" "orange"    "orange"   
[15] "orange"    "Imprimeur" "orange"    "orange"    "orange"    "Imprimeur" "Imprimeur"
[22] "Imprimeur" "orange"    "Auteur"    "Auteur"    "orange"    "Imprimeur"
#Je continue avec les autres valeurs
to_colors<-replace(to_colors,to_colors=="Auteur","green")
to_colors<-replace(to_colors,to_colors=="Imprimeur","red")
#J'obtiens un nouvel objet avec des couleurs à la place des labels
to_colors
 [1] "green"  "orange" "orange" "orange" "red"    "red"    "red"    "orange" "orange"
[10] "orange" "orange" "red"    "orange" "orange" "orange" "red"    "orange" "orange"
[19] "orange" "red"    "red"    "red"    "orange" "green"  "green"  "orange" "red"   

Je peux désormais appliquer cette couleur à chaque nœud

#J'ai une colonne couleur qui est vide, que je vais remplir avec l'objet `to_colors` que je viens de créer
V(data)$color
#Je remplace la couleur du graphe avec celle que je viens de définir
V(data)$color <- to_colors
#Le graphe change de couleur
plot(data)

Je peux faire la même opération avec la forme des nœuds, et améliorer encore le rendu.

ATTENTION: le rendu dans RStudio n’est pas forcément optimum: pensez l’ouvrir dans une nouvelle fenêtre pour voir le résultat.

#On change la forme du nœud en fonction du label
to_shape<-V(data)$type
to_shape<-replace(to_shape,to_shape=="Auteur","square")
to_shape<-replace(to_shape,to_shape=="Imprimeur","circle")
to_shape<-replace(to_shape,to_shape=="Libraire","sphere")
#Je peux à nouveau changer l'objet igraph
V(data)$color <- to_colors
V(data)$label.color <- "black"
#E(data)$edge.color <- "gray80"
#ou bien intervenir directement dans les paramètres du graphe
plot(data,
     vertex.label.degree=2,
     #on injecte le vecteur avec les formes que nous venons de créer
     vertex.shape=to_shape,
     #taille des nœuds
     vertex.size = 10,
     #taille de la police
     vertex.label.cex=0.7
     ) 
title("mon graphe", sub="premier test")
#J'ajoute une petite légende
legend(x=-1.5, y=-1.1, c("Auteur","Libraire", "Imprimeur"), pch=21,
       col="#777777", pt.bg=c("green", "orange", "red"), pt.cex=2, cex=.8, bty="n", ncol=1)

Nous avons encore un problème: les relations multiples sont toutes dessinées, car elles sont restées dans le tableau. Quelles sont-elles?

Deux problèmes sont possibles: * Une boucle (loop) est un nœud relié par une arête à lui-même * Un multiple (multiple) sont deux nœuds reliés plusieurs fois ensemble. N.B. si le graph est dirigé 2->1 n’est pas un multiple de 1->2, mais s’il est dirigé oui.

which_loop(data)
  [1] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
 [15] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
 [29] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
 [43] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
 [57] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
 [71] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
 [85] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
 [99] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[113] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[127] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[141] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[155] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[169] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[183] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[197] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[211] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[225] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[239] FALSE FALSE FALSE FALSE
which_multiple(data)
  [1] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
 [15] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE  TRUE FALSE FALSE FALSE  TRUE
 [29]  TRUE FALSE  TRUE FALSE  TRUE  TRUE FALSE  TRUE FALSE  TRUE FALSE  TRUE FALSE  TRUE
 [43] FALSE FALSE FALSE FALSE  TRUE FALSE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE
 [57]  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE
 [71]  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE FALSE  TRUE FALSE FALSE  TRUE  TRUE FALSE
 [85] FALSE FALSE  TRUE  TRUE  TRUE  TRUE  TRUE FALSE FALSE FALSE  TRUE  TRUE  TRUE  TRUE
 [99] FALSE FALSE FALSE  TRUE  TRUE  TRUE  TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[113] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE  TRUE  TRUE FALSE  TRUE  TRUE FALSE
[127]  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE
[141]  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE FALSE  TRUE  TRUE  TRUE  TRUE
[155]  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE FALSE  TRUE  TRUE  TRUE FALSE  TRUE  TRUE  TRUE
[169]  TRUE  TRUE  TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE  TRUE
[183] FALSE FALSE  TRUE FALSE FALSE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE
[197]  TRUE  TRUE  TRUE  TRUE FALSE FALSE  TRUE  TRUE  TRUE  TRUE FALSE  TRUE  TRUE FALSE
[211] FALSE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE FALSE FALSE  TRUE  TRUE  TRUE FALSE
[225] FALSE FALSE FALSE FALSE FALSE FALSE  TRUE  TRUE  TRUE FALSE  TRUE  TRUE FALSE FALSE
[239]  TRUE  TRUE FALSE FALSE

Comme j’ai de nombreux multiples, je vais les transformer en poids pour chaque arête

#Je compte les multiples pour chaque arête
count_multiple(data)
  [1]  5  7  5  2  1  6  5  5  2  1  4  5  2  1  5  2  1  4  1  1  1  1 13  6  1  1  1  5
 [29]  5  4  7  6  6  5  4  5  4  4  4  5  4  4  4  4  3  6  5  4  5  5  4  7  6  6  5  4
 [57]  5  4  4  4  5  4  4  4  4  3  6  5  4  7  6  6  6  5  4  7  6  1  6  1  1  5  5  2
 [85]  2  2  4  7  6  2  5  2  2  2  4  5  4  2  2  2  2  4  5  4  2  2  2  2  2  2  1  2
[113]  2  2  2  1  2  2  2  1  4  4  1  6  2  1  5  2  5  2  2  4  7  6  6  2  5  2  2  4
[141]  5  4  4  2  2  2  2  2  2  1  2  2  4  5  4  4  2  2  2  2  1  2  2  2  1  4  4  3
[169]  6  5  4  1  1  1  1  1  1  1  1  1  1 13 11 10 13  1  1 13 11 10 13 11 10 13 11 10
[197] 13 11 10 13  1  1 11 13 11 10  3 11 13  3  3 10  3 11 13  3  3 10  1  2  3 13 11  1
[225]  1  1  1  1  1  1  3  3 10  1 13 11  1  1 10  2  1  1
#Je fais une copie pour travailler dessus (si j'ai besoin des données originales plus tard)
data_simplified <- data
#Je copie-colle le nombre de multiple par arête dans la colonne des poids
E(data_simplified)$weight <- count_multiple(data_simplified)
#je retire les doublons (les multiples) avec la fonction simplify()
data_simplified <- simplify(data_simplified)

J’affiche mon nouveau graph: la largeur de l’arête dépend désormais du poids

E(data_simplified)$width <-E(data_simplified)$weight/2
plot(data_simplified,
     #pas de courbure de l'arête
     edge.curved=0,
     #distance entre le label et le nœud
     vertex.label.dist=1,
     #Choix de la police
     vertex.label.family="Times",
     #Choix de la forme
     vertex.shape=to_shape,
     # Taile du nœud
     vertex.size = 6,
     #taille de la police
     vertex.label.cex=0.6
     )
title("Et voilà!")
#J'ajoute une petite légende
legend(x=-2, y=-0.5, c("Auteur","Libraire", "Imprimeur"), pch=21,
       col="#777777", pt.bg=c("green", "orange", "red"), pt.cex=1, cex=.8, bty="n", ncol=1)

3 Tracé de graphe

Repartons de zero

Il existe différentes visualisation, algorithmes, etc. La logique est toujours la même: je pré-traite mon objet igraph avec une fonction spécifique au tracé choisi, et j’utilise le résultat de ce prétraitement comme valeur du paramètre layout. Ici, le circular layout:

to_circle<-layout_in_circle(data)
plot(data, layout=to_circle, vertex.size=1)

Il existe une multitude de layouts. Je peux tous les afficher d’un coup, pour jeter un coup d’œil à la forme qu’ils prennent, et choisir celui qui m’intéresse le plus

layouts <- grep("^layout_", ls("package:igraph"), value=TRUE)[-1] 
# J'en retire certains si je veux
layouts <- layouts[!grepl("bipartite|merge|norm|sugiyama|tree", layouts)]
#je prépare la mise en page du résultat
par(mfrow=c(3,3), mar=c(1,1,1,1))
#Je fais un boucle: un graph par itération
for (layout in layouts) {
  print(layout)
  l <- do.call(layout, list(data)) 
  plot(data_simplified, edge.arrow.mode=0, layout=l, main=layout) }

S’il y en a un qui m’intéresse, je peux l’appliquer de la même manière que pour le cercle.

Evidemment, je ne dois choisir un graphe adapté…

data("Koenigsberg")
plot(Koenigsberg)

Il semble que la forme en étoile soit bien adaptée, étant donné la centralité de Molière:

to_star<-layout_as_star(data)
plot(data, layout=to_star, vertex.size=0.1)

3.1 Les algorithmes forced base

Les tracés les plus importants sont les forced base, qui nécessitent des algorithmes particuliers. Regrdons-les en détail.

3.1.1 Fruchterman Reingold

Fruchterman, Thomas M. J.; Reingold, Edward M. (1991), “Graph Drawing by Force-Directed Placement”, Software – Practice & Experience, Wiley, 21 (11): 1129–1164, doi:10.1002/spe.4380211102.

Plus d’informations ici

Le algorithme est assez comppliqué, et le temprs de calcul conséquent. On l’utilise peu avec des grandes bases de données (plus de 10 000 nœuds).

layout_fr<-layout_with_fr(data_simplified)
E(data_simplified)$width <-E(data_simplified)$weight
plot(data_simplified, layout=layout_fr,
     #J'ajoute les poids
     weight=TRUE,
     #pas de courbure de l'arête
     edge.curved=0)

On peut jouer sur les paramètres et augmenter le nombre d’itération

#Je passe sur 2 colonnes, 2 rangs
par(mfrow=c(2, 2))
#J'ajuste la marge pour le titre
par(oma=c(1,1,1,1))
## layout_with_fr
plot.igraph(data_simplified, layout = layout_with_fr(data_simplified, niter = 1), main = 1)
plot.igraph(data_simplified, layout = layout_with_fr(data_simplified, niter = 5), main = 5)
plot.igraph(data_simplified, layout = layout_with_fr(data_simplified, niter = 10), main = 10)
plot.igraph(data_simplified, layout = layout_with_fr(data_simplified, niter = 20), main = 20)

plot.igraph(data_simplified, layout = layout_with_fr(data_simplified, niter = 50), main = 50)
plot.igraph(data_simplified, layout = layout_with_fr(data_simplified, niter = 75), main = 75)
plot.igraph(data_simplified, layout = layout_with_fr(data_simplified, niter = 100), main = 100)
plot.igraph(data_simplified, layout = layout_with_fr(data_simplified, niter = 150), main = 150)

plot.igraph(data_simplified, layout = layout_with_fr(data_simplified, niter = 200), main = 200)
plot.igraph(data_simplified, layout = layout_with_fr(data_simplified, niter = 300), main = 300)
plot.igraph(data_simplified, layout = layout_with_fr(data_simplified, niter = 500), main = 500)
plot.igraph(data_simplified, layout = layout_with_fr(data_simplified, niter = 700), main = 700)
title("No. of Iterations (layout_with_fr)", outer = TRUE)
par(mfrow=c(1, 1))
par(oma=c(0,0,0,0))

Voyons le résultat apèrs 700 itérations:

## J'épaissis l'arête en fonction du poids
E(data_simplified)$width <-E(data_simplified)$weight
plot.igraph(data_simplified,
            layout = layout_with_fr(data_simplified, niter = 700),
            main = 700,
            #pas de courbure de l'arête
            edge.curved=0,
            #taille de la police
            vertex.label.cex=0.6,
            # Taile du nœud
            vertex.size = 8)
title("700 itérations", outer = TRUE)

3.1.2 DrL

Le nom a changé plusieurs fois: d’abord rebaptisé vxOrd, on parle d’OpenOrd.

  • Martin, S., Brown, W.M., Klavans, R., Boyack, K.W., DrL: Distributed Recursive (Graph) Layout. SAND Reports, 2008. 2936: p. 1-10.
  • S. Martin, W. M. Brown, R. Klavans, and K. Boyack (to appear, 2011), “OpenOrd: An Open-Source Toolbox for Large Graph Layout,” SPIE Conference on Visualization and Data Analysis (VDA).

Plus d’informations ici

Il va tenter de faire ressortir au maximum des grands clusters très nets en coupant les liens les plus longs. Evidemment cet algorithme nécessite des graphes de grande taille, nous chargeons donc un gros jeu de données tiré du package igraphdata.

data("USairports")
#On trace le graphe
layout_drl <- layout.drl(USairports)
plot(USairports, layout=layout_drl, main="DrL")

Nous pouvons comparer l’effet de ce découpage avec celui effectué par l’algorithme précédent, Fruchterman Reingold

par(mfrow=c(1, 2))
par(oma=c(0,0,2,0))
plot(USairports, layout=layout_with_fr(USairports), weight=T, main="FR")
plot(USairports, layout=layout_drl, main="DrL")

3.2 le Geolayout

J’ai préparé un tout petit jeu de données avec des coordonnées géographiques

nodes_geo <- as.data.frame(read.csv(file="data/geo/nodes.csv", sep = "\t", header = FALSE))
edges_geo <- as.data.frame(read.csv(file="data/geo/edges.csv", sep = "\t", header = FALSE))
#Je donne un nom aux colonnes de chaque data.frame
colnames(nodes_geo) <- c("id", "label","lat","long")
colnames(edges_geo) <- c("from", "to")
nodes_geo
  id     label      lat      long
1  1     Paris 48.86472  2.349014
2  2 Bruxelles 50.85045  4.348780
3  3    Geneve 46.20439  6.143158
4  4   Londres 51.50853 -0.125740
edges_geo
  from to
1    1  2
2    1  3
3    1  4

Je transforme ces deux objets en données igraph, qui vont me permettre de faire mes analyses de réseau par la suite.

data_geo <- graph_from_data_frame(d=edges_geo, vertices=nodes_geo, directed=F) 
class(data_geo)
plot(data_geo)

Je projette ce réseau sur une carte, en plaçant les nœuds en fonction de leurs coordonnées géographiques

#Je définis les lat et long de mon cadre
western_europe<-c(left = -12, bottom = 40, right = 20, top = 55)
#Je récupère mon fond de carte selon les dimensions prévues supra
map <- get_stamenmap(western_europe, zoom=6, source="stamen", maptype="toner-lite", filetype="png")
#Je crée une carte à partir de mon fond de carte
p<-ggmap(map)
#J'ajoute les arêtes
p = p + geom_edgeset(aes(x=long, y=lat), data_geo, colour=gray(0.1, 0.3), size=1)
#J'ajoute les nœuds
p = p + geom_nodeset(aes(x=long, y=lat), data_geo, size=3, colour="red")
#J'affiche le tout
p

4 La force des liens

4.1 Les mesures

Densité (density): la proportion de liens dans un réseau relativement au total des liens possibles.

edge_density(data)
[1] 0.6894587

Centralité de proximité: Distance moyenne du nœud à tous les autres nœuds (Closeness)

closeness.cent <- closeness(data)
closeness.cent
         1          2          3          4          5          6          7          8 
0.03846154 0.02439024 0.02500000 0.02439024 0.02439024 0.02173913 0.02564103 0.02040816 
         9         10         12         13         14         15         16         17 
0.02380952 0.02380952 0.02439024 0.02040816 0.02380952 0.02380952 0.02380952 0.02173913 
        18         19         20         21         22         23         24         25 
0.02083333 0.02083333 0.02083333 0.02083333 0.02000000 0.02000000 0.02127660 0.02127660 
        26         27         28 
0.02173913 0.02040816 0.02000000 

Pour rappel, les noms attachés sont accessibles ainsi:

cbind(V(data)$label,closeness.cent)
                              closeness.cent      
1  "Molière"                  "0.0384615384615385"
2  "Guillaume de Luyne"       "0.024390243902439" 
3  "Claude Barbin"            "0.025"             
4  "Charles de Sercy"         "0.024390243902439" 
5  "Jean Hénault"             "0.024390243902439" 
6  "François Noël"            "0.0217391304347826"
7  "Christophe Journel"       "0.0256410256410256"
8  "Sieur de Neuf-Villenaine" "0.0204081632653061"
9  "Jean Ribou"               "0.0238095238095238"
10 "Jean Guignard"            "0.0238095238095238"
12 "Gabriel Quinet"           "0.024390243902439" 
13 "François II Noël"         "0.0204081632653061"
14 "Thomas Jolly"             "0.0238095238095238"
15 "Louis Billaine"           "0.0238095238095238"
16 "Estienne Loyson"          "0.0238095238095238"
17 "Claude Blageart"          "0.0217391304347826"
18 "Pierre Trabouillet"       "0.0208333333333333"
19 "Nicolas Le Gras"          "0.0208333333333333"
20 "Théodore Girard"          "0.0208333333333333"
21 "Etienne Maucroy"          "0.0208333333333333"
22 "Claude II Calleville"     "0.02"              
23 "Claude Audinet"           "0.02"              
24 "Pierre Le Monnier"        "0.0212765957446809"
25 "Pierre Corneille"         "0.0212765957446809"
26 "Philippe Quinault"        "0.0217391304347826"
27 "Pierre Promé"             "0.0204081632653061"
28 "François Muguet"          "0.02"              

Centralité d’intermédiarité: Nombre de fois que le nœud se trouve sur le plus court chemin entre deux autres nœuds (Betweenness)

closeness.bet <- betweenness(data)
closeness.bet
          1           2           3           4           5           6           7 
222.8397763   0.9600000   4.3209524   0.9600000   0.3900000   0.0000000   5.0683883 
          8           9          10          12          13          14          15 
  0.0000000  10.2680258   0.0000000   2.3714286   0.0000000   0.0000000   0.0000000 
         16          17          18          19          20          21          22 
  0.0000000   0.9166667   0.0000000   0.0000000   0.0000000   0.0000000   0.0000000 
         23          24          25          26          27          28 
  0.0000000   0.0000000   0.0000000   0.9047619   0.0000000   0.0000000 

Centralité de vecteurs propres: Score d’autorité attribué à un nœud en fonction du score de ses voisins. (Eigenvector).

closeness.eig <- eigen_centrality(data)
closeness.eig$vector
         1          2          3          4          5          6          7          8 
1.00000000 0.56536647 0.65991521 0.56536647 0.23172674 0.10190675 0.55278661 0.06001095 
         9         10         12         13         14         15         16         17 
0.55255801 0.48574803 0.58647420 0.06403130 0.27379413 0.27379413 0.27379413 0.49263907 
        18         19         20         21         22         23         24         25 
0.03116947 0.03116947 0.03116947 0.03116947 0.04425426 0.04425426 0.17947299 0.06611127 
        26         27         28 
0.09469017 0.05829650 0.03120315 

Centralité de degré: Nombre de connexions du nœud (Degree)

closeness.deg <- degree(data_simplified)
closeness.deg
 1  2  3  4  5  6  7  8  9 10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 
82 36 42 36 15  6 33  3 33 30 36  3 18 18 18 27  4  4  4  4  2  2 11  5  7  3  2 

On peut réutiliser ces données pour la visualisation, en ajustant la taille des nœuds à la centralité de degré

V(data_simplified)$size <- (closeness.deg*0.3)
plot(data_simplified, layout=layout_fr, main="FR")

On peut ajuster cette taille avec d’autres mesures de centralité, comme la centralité de vecteur

V(data_simplified)$size <- (closeness.eig$vector*30)
plot(data_simplified, layout=layout_fr, main="FR")

4.2 Un exemple d’analyse de la centralité

Tentons une approche plus pratique avec un réseau célèbre: celui de la Florence de la Renaissance (disponible dans le package netrankr).

data("florentine_m")
#Une famille n'est pas reliée aux autres: la famille Pucci
degree(florentine_m)==0
Acciaiuol   Albizzi Barbadori  Bischeri Castellan    Ginori  Guadagni Lambertes    Medici 
    FALSE     FALSE     FALSE     FALSE     FALSE     FALSE     FALSE     FALSE     FALSE 
    Pazzi   Peruzzi     Pucci   Ridolfi  Salviati   Strozzi Tornabuon 
    FALSE     FALSE      TRUE     FALSE     FALSE     FALSE     FALSE 
#On la retire pour simplifier la visualisation
florence <- delete_vertices(florentine_m,which(degree(florentine_m)==0))

J’obtiens un joli graphe:

plot.igraph(florence, layout = layout_with_fr(florence, niter = 500),
                      main = "Florence au XVème s.")

Je peux proportionner la taille des nœuds en fonction de la fortune de chaque famille:

plot(florence,
     layout = layout_with_fr(florence, niter = 500),
     vertex.label.cex=V(florence)$wealth*0.012,
     vertex.size=V(florence)$wealth*0.2)

Mais est-ce que la richesse fait tout? Probablement pas… tentons d’évaluer la centralité des différentes familles

#Je fais un data-frame à partir de différents calculs de centralité
cent.data_frame <- data.frame(
  degree = degree(florence),
  betweenness = betweenness(florence),
  closeness = closeness(florence),
  eigenvector = eigen_centrality(florence)$vector,
  subgraph = subgraph_centrality(florence))
#Je peux accéder au résultat sous la forme de tableau qui résume toutes les données
View(cent.data_frame)
# Je donne le nom de la famille la plus centrale pour chaque mesure
V(florence)$name[apply(cent.data_frame,2,which.max)]
[1] "Medici" "Medici" "Medici" "Medici" "Medici"

5 Visualiser

Il est possible de proposer une foule de visualisation. Par exemple, il est possible de remplacer les labels par la distance qui sépare un nœud d’un autre – ici, Thomas Jolly.

dist.thoJo <- distances(data, v=V(data)[label=="Thomas Jolly"], to=V(data), weights=NA)
# Set colors to plot the distances:
green.dark <- colorRampPalette(c("darkgreen", "lightgreen"))
col <- green.dark(max(dist.thoJo)+1)
col <- col[dist.thoJo+1]
plot(data, vertex.color=col, vertex.label=dist.thoJo)

On peut mettre en valeur le chemin le plus court entre deux poins

mon_chemin <- shortest_paths(data, 
                            from = V(data)[label=="Thomas Jolly"], 
                             to  = V(data)[label=="Pierre Corneille"],
                            #je colorie le nœud et l'arête
                             output = "both")
# On génère une couleur pour les arêtes en fonction du chemin
couleur_arc <- rep("gray80", ecount(data))
couleur_arc[unlist(mon_chemin$epath)] <- "orange" 
"Couleur des arcs"
couleur_arc #cf. 128 et 219
# On génère une largeur pour l'arête en fonction du chemin
largeur_arc <- rep(2, ecount(data))
largeur_arc[unlist(mon_chemin$epath)] <- 6
"Largeur des arcs"
largeur_arc #cf. 128 et 219
# Generate node color variable to plot the path:
coleur_noeud <- rep("gray40", vcount(data))
coleur_noeud[unlist(mon_chemin$vpath)] <- "gold"
"Les nœuds"
coleur_noeud #cf. 1 et 13
plot(data, vertex.color=coleur_noeud, edge.color=couleur_arc, 
     edge.width=largeur_arc, edge.arrow.mode=0)

On peut aussi regrouper en cluster les données, que l’on représente en dendogramme, comme pour la stylométrie

ceb <- cluster_edge_betweenness(data) 
dendPlot(ceb, mode="hclust")

Je projette ensuite ma classification sur mon graph

plot(ceb, data) 

On peut l’afficher en 3d. Pour cela j’utilise le paramètre dim=3 pour mon layout.

coords <- layout_with_fr(data_simplified, dim=3)
open3d()
rglplot(data, layout=coords)

Je peux faire une sauvegarde, notamment en HTML pour l’ouvrir dans le navigateur

dirfolder=getwd()
#open3d plutôt que rgl.open() pour une sauvegarde
open3d()
rglplot(data_simplified, layout=coords)
#Je prépare l'angle
rgl.viewpoint(theta=0, phi=0)
#Sauvegarder un screenshot (en png)
rgl.snapshot(paste(dirfolder,"monGRaph3d.png",sep=""), fmt="png", top=TRUE)
#Sauvegarde en html
rglfolder=writeWebGL(dir = paste(dirfolder,"first_net3d",sep=""), width=900)
#J'ouvre le résultat dans le navigateur
browseURL(rglfolder)

Je peux produire une visualisation interactive directement dans R. Je prépare les données

# je convertis mon igraphe en une liste  composée de deux data.frames (nodes et edges)
data_3d_vis <- toVisNetworkData(data)
# Pour le menu déroulant (cf infra)
names <- sort(data_3d_vis$nodes$label)

Et je lance une visualisation en 3D

visNetwork(nodes = data_3d_vis$nodes,
           edges = data_3d_vis$edges,
           main = "Mon graphe interactif",
           submain = "Alogirhtme de Fruchterman–Reingold",
           footer = "Wow") %>%
  #Je trace le graphe
  visIgraphLayout(layout = "layout_with_fr", 
                  smooth = FALSE,
                  #J'ajoute de la dynamique (cf. _infra_)
                  physics = TRUE
                )

Je rajoute des options de visualisation, comme une modification des nœuds s’ils sont sélectionnés, ou un selecteur sous la forme de liste déroulante

visNetwork(nodes = data_3d_vis$nodes,
           edges = data_3d_vis$edges,
           main = "Mon graphe interactif",
           submain = "Alogirhtme de Fruchterman–Reingold",
           footer = "Wow") %>%
  #Je trace le graphe
  visIgraphLayout(layout = "layout_with_fr", 
                  smooth = FALSE,
                  #J'ajoute de la dynamique (cf. _infra_)
                  physics = TRUE
                ) %>%
  #Je mets en valeur les nœuds liés
  visOptions(highlightNearest = list(enabled = TRUE,
                                     #séparés de 1 degré
                                     degree = 1,
                                     #il s'illuminent quand la souris passe sur le nœud
                                     hover = TRUE),
             #Je crée un sélecteur
             nodesIdSelection = list(enabled = TRUE,
                                     values = names))

Je vais avoir besoin “d’écarter” mon graphe, en ajoutant de la répulsion entre les nœuds (ce qui n’est pas tâche facile…)

data_3d_vis_plot <- visNetwork(nodes = data_3d_vis$nodes,
                               edges = data_3d_vis$edges,
                               main = "Mon graphe interactif",
                               submain = "Alogirhtme de Fruchterman–Reingold",
                               footer = "Wow") %>%
                    #Je trace le graphe
                    visIgraphLayout(layout = "layout_with_fr", 
                                    smooth = FALSE,
                                    #J'ajoute de la dynamique (cf. _infra_)
                                    physics = TRUE
                                    ) %>%
                    #Je mets en valeur les nœuds liés
                    visOptions(highlightNearest = list(enabled = TRUE,
                                                      #séparés de 1 degré
                                                      degree = 1,
                                                      #passage souris
                                                      hover = TRUE),
                              #Je crée un sélecteur
                              nodesIdSelection = list(enabled = TRUE,
                                                      values = names)
                              ) %>%
                    #taille des nœuds
                    visNodes(size = 50) %>%
                    #couleur des arêtes
                    visEdges(color = list(highlight = "lightgray")) %>%
                    #Je paramètre la répulsion
                    visPhysics(#Vélocité des nœuds
                               maxVelocity = 1,
                               #type de répulsion hiérarchique
                               solver = "forceAtlas2Based",
                               #paramètres du forceAtlas2Based
                               #la `gravitationalConstant` décrit la répulsion (l'écartement entre les nœuds), le chiffre est donc négatif, sinon oncrée de l'attraction
                               forceAtlas2Based = list(gravitationalConstant = -1000)
                     )
data_3d_vis_plot

6 Sauvegardes

On sauvegarde le résultat

write_graph(data, "edgelist.txt", format="edgelist")
svg(file="monGraph.svg")
plot(data)
dev.off()
png(file="monGraph.png")
plot(data)
dev.off()
100% center

100% center

100% center

100% center

LS0tCnRpdGxlOiAiQ291cnNfR2VuZXZlXzgiCmF1dGhvcjogIlNpbW9uIEdhYmF5IgpkYXRlOiAiYHIgU3lzLkRhdGUoKWAiCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgdG9jOiB0cnVlCiAgICB0b2NfZmxvYXQ6IHRydWUKICAgIG51bWJlcl9zZWN0aW9uczogdHJ1ZQoKLS0tCgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFLCByZXN1bHRzID0gRkFMU0UsIGZpZy5zaG93PSdob2xkJykKYGBgCgojIFByw6lwYXJhdGlmcwoKYGBge3J9CnNldHdkKCJ+L0dpdEh1Yi9Db3Vyc18yMDIwX1VuaUdFL0NvdXJzX0dlbmV2ZV84IikKI2plIGNoYXJnZSBsZXMgZG9ubsOpZXMgcXVlIGwnZW5zZWlnbmFudCBhIHByw6lwYXLDqSBwb3VyIMOpdml0ZXIgbGVzIHByb2Jsw6htZXMKI2xvYWQoIkNvdXJzX0dlbmV2ZV84LlJEYXRhIikKYGBgCgpgYGB7cn0KaWYoIXJlcXVpcmUoImRldnRvb2xzIikpewogIGluc3RhbGwucGFja2FnZXMoImRldnRvb2xzIikKICBsaWJyYXJ5KGRldnRvb2xzKQp9CmlmKCFyZXF1aXJlKCJpZ3JhcGgiKSl7CiAgaW5zdGFsbC5wYWNrYWdlcygiaWdyYXBoIikKICBsaWJyYXJ5KGlncmFwaCkKfQppZighcmVxdWlyZSgidGlkeXZlcnNlIikpewogIGluc3RhbGwucGFja2FnZXMoInRpZHl2ZXJzZSIpCiAgbGlicmFyeSh0aWR5dmVyc2UpCn0KaWYoIXJlcXVpcmUoInRpZHlncmFwaCIpKXsKICBpbnN0YWxsLnBhY2thZ2VzKCJ0aWR5Z3JhcGgiKQogIGxpYnJhcnkodGlkeWdyYXBoKQp9CmlmKCFyZXF1aXJlKCJnZ3JhcGgiKSl7CiAgaW5zdGFsbC5wYWNrYWdlcygiZ2dyYXBoIikKICBsaWJyYXJ5KGdncmFwaCkKfQppZighcmVxdWlyZSgicWdyYXBoIikpewogIGluc3RhbGwucGFja2FnZXMoInFncmFwaCIpCiAgbGlicmFyeShxZ3JhcGgpCn0KaWYoIXJlcXVpcmUoImNvcnJyIikpewogIGluc3RhbGwucGFja2FnZXMoImNvcnJyIikKICBsaWJyYXJ5KGNvcnJyKQp9CmlmKCFyZXF1aXJlKCJ2aXNOZXR3b3JrIikpewogIGluc3RhbGwucGFja2FnZXMoInZpc05ldHdvcmsiKQogIGxpYnJhcnkodmlzTmV0d29yaykKfQppZighcmVxdWlyZSgibmV0d29ya0QzIikpewogIGluc3RhbGwucGFja2FnZXMoIm5ldHdvcmtEMyIpCiAgbGlicmFyeShuZXR3b3JrRDMpCn0KaWYoIXJlcXVpcmUoIkZvcmNlQXRsYXMyIikpewogIGRldnRvb2xzOjppbnN0YWxsX2dpdGh1YigiYW5hbHl4Y29tcGFueS9Gb3JjZUF0bGFzMiIpCiAgbGlicmFyeShGb3JjZUF0bGFzMikKfQppZighcmVxdWlyZSgicmdsIikpewogIGluc3RhbGwucGFja2FnZXMoInJnbCIpCiAgbGlicmFyeShyZ2wpCn0KaWYoIXJlcXVpcmUoImlncmFwaGRhdGEiKSl7CiAgaW5zdGFsbC5wYWNrYWdlcygiaWdyYXBoZGF0YSIpCiAgbGlicmFyeShpZ3JhcGhkYXRhKQp9CmlmKCFyZXF1aXJlKCJuZXRyYW5rciIpKXsKICBpbnN0YWxsLnBhY2thZ2VzKCJuZXRyYW5rciIpCiAgbGlicmFyeShuZXRyYW5rcikKfQppZighcmVxdWlyZSgicG9wZ3JhcGgiKSl7CiAgZGV2dG9vbHM6Omluc3RhbGxfZ2l0aHViKCJkeWVybGFiL3BvcGdyYXBoIikKICBsaWJyYXJ5KHBvcGdyYXBoKQp9CmlmKCFyZXF1aXJlKCJnZ21hcCIpKXsKICBpbnN0YWxsLnBhY2thZ2VzKCJnZ21hcCIpCiAgbGlicmFyeShnZ21hcCkKfQpgYGAKCkplIGNoYXJnZSBtZXMgZGV1eCBmaWNoaWVyczogY2VsdWkgYXZlYyBsZXMgbsWTdWRzIChgbm9kZXMuY3N2YCkgZXQgY2VsdWkgYXZlYyBsZXMgYXLDqnRlcyAoYGVkZ2VzLmNzdmApLgoKYGBge3J9Cm5vZGVzIDwtIGFzLmRhdGEuZnJhbWUocmVhZC5jc3YoZmlsZT0iZGF0YS9iYXNpYy9ub2Rlcy5jc3YiLCBzZXAgPSAiXHQiLCBoZWFkZXIgPSBGQUxTRSkpCmVkZ2VzIDwtIGFzLmRhdGEuZnJhbWUocmVhZC5jc3YoZmlsZT0iZGF0YS9iYXNpYy9lZGdlcy5jc3YiLCBzZXAgPSAiXHQiLCBoZWFkZXIgPSBGQUxTRSkpCiNKZSBkb25uZSB1biBub20gYXV4IGNvbG9ubmVzIGRlIGNoYXF1ZSBkYXRhLmZyYW1lCmNvbG5hbWVzKG5vZGVzKSA8LSBjKCJpZCIsICJsYWJlbCIsInR5cGUiKQpjb2xuYW1lcyhlZGdlcykgPC0gYygiZnJvbSIsICJ0byIpCiNKZSBjb250csO0bGUgcXVlIHRvdXQgZXN0IGVuIG9yZHJlCmBgYAoKSidhZmZpY2hlIGxlcyBwcmVtaWVycyDDqWzDqW1lbnRzIGRlIGNoYXF1ZSBmaWNoaWVyLCBldCBqZSBjb21wdGUgbGVzIHJhbmdzIHBvdXIgbWUgZmFpcmUgdW5lIGlkw6llIGRlIGNlIHF1aSBzZSB0cm91dmUgZGFucyBtZXMgZG9ubsOpZXMKCmBgYHtyLHJlc3VsdHM9J2hvbGQnfQpoZWFkKG5vZGVzKQpoZWFkKGVkZ2VzKQpucm93KG5vZGVzKTsgbGVuZ3RoKHVuaXF1ZShub2RlcyRpZCkpCm5yb3coZWRnZXMpOyBucm93KHVuaXF1ZShlZGdlc1ssYygiZnJvbSIsICJ0byIpXSkpCmBgYAoKSmUgdHJhbnNmb3JtZSBjZXMgZGV1eCBvYmpldHMgZW4gZG9ubsOpZXMgYGlncmFwaGAsIHF1aSB2b250IG1lIHBlcm1ldHRyZSBkZSBmYWlyZSBtZXMgYW5hbHlzZXMgZGUgcsOpc2VhdSBwYXIgbGEgc3VpdGUuCgpgYGB7cixyZXN1bHRzPSdob2xkJ30KZGF0YSA8LSBncmFwaF9mcm9tX2RhdGFfZnJhbWUoZD1lZGdlcywgdmVydGljZXM9bm9kZXMsIGRpcmVjdGVkPUYpIApjbGFzcyhkYXRhKQpgYGAKCk1lcyBkb25uw6llcyBzZSBwcsOpc2VudGVudCBzb3VzIGNldHRlIGZvcm1lOgoKYGBge3IscmVzdWx0cz0naG9sZCd9CmRhdGEKYGBgCgpKZSBwZXV4IGTDqXNvcm1haXMgYWZmaWNoZXIgbGVzIG7Fk3VkcywgbGVzIGFyw6p0ZXMgZGUgY2V0dGUgbWFuacOocmUuIEplIHBldXggYXVzc2kgc8OpbGVjdGlvbm5lciBjZXJ0YWluZXMgY29sb25uZXMgcG91ciBjaGFxdWUgZmljaGllciBkJ3VuZSBtYW5pw6hyZSBwYXJ0aWN1bGnDqHJlIGF1eCBvYmpldHMgYGlncmFwaGAKCmBgYHtyLHJlc3VsdHM9J2hvbGQnfQojZWRnZXMKRShkYXRhKQojbm9kZXMKVihkYXRhKQojbm9kZXMgbGFiZWxzClYoZGF0YSkkbGFiZWwKI25vZGVzIHR5cGVzClYoZGF0YSkkdHlwZQpgYGAKCiMgTW9uIHByZW1pZXIgZ3JhcGhlCgpKZSBwZXV4IGTDqXNvcm1haXMgZmFicmlxdWVyIG1vbiByw6lzZWF1IGF2ZWMgbGEgZm9uY3Rpb24gYHBsb3RgOgoKYGBge3J9CnBsb3QoZGF0YSkgCmBgYAoKSWwgZXhpc3RlIHVuZSBmb25jdGlvbiBhbHRlcm5hdGl2ZSBgcGxvdC5pZ3JhcGhgLCBxdWkgZmFpdCBsYSBtw6ptZSBjaG9zZQoKYGBge3J9CnBsb3QuaWdyYXBoKGRhdGEpIApgYGAKCklsIGV4aXN0ZSBlbmZpbiB1bmUgZm9uY3Rpb24gYHRrcGxvdGAgcXVpIGVzdCB1biBwcm90b3R5cGUgZCdpbnRlcmZhY2UgdXRpbGlzYXRldXI6CgpgYGB7cixpbmNsdWRlPVRSVUV9CiN0a3Bsb3QoZGF0YSkKYGBgCgpKZSBkaXNwb3NlIGQndW4gZ3JhbmQgbm9tYnJlIGRlIHBhcmFtw6h0cmVzIHBvdXIgbW9kaWZpZXIgbCdhcHBhcmVuY2UgZGUgbW9uIGdyYXBoIGV0IGxlIHJlbmRyZSAoc2kgb24gZW4gYSBsZSB0YWxlbnQpIGVzdGjDqXRpcXVlOgoKYGBge3J9CnBsb3QoZGF0YSwKICAgICAjY291cmJ1cmUgZGUgbCdhcsOqdGUKICAgICBlZGdlLmN1cnZlZD0wLjEsCiAgICAgI2NvdWxldXIgZGUgbCdhcsOqdGUKICAgICBlZGdlLmNvbG9yPSJvcmFuZ2UiLAogICAgICNjb3VsZXVyIGR1IG7Fk3VkCiAgICAgdmVydGV4LmNvbG9yPSJncmVlbiIsCiAgICAgI2NvdWxldXIgZHUgY29udG91ciBkdSBuxZN1ZAogICAgIHZlcnRleC5mcmFtZS5jb2xvcj0iIzU1NTU1NSIsCiAgICAgI2NvdWxldXIgZGUgbCfDqXRpcXVldHRlIGR1IG7Fk3VkCiAgICAgdmVydGV4LmxhYmVsLmNvbG9yPSJkYXJrcmVkIiwKICAgICAjY29udGVudSBkZSBsJ8OpdGlxdWV0dGUgZHUgbsWTdWQKICAgICB2ZXJ0ZXgubGFiZWw9VihkYXRhKSR0eXBlLAogICAgICN0YWlsbGUgZGUgbGEgcG9saWNlCiAgICAgdmVydGV4LmxhYmVsLmNleD0xKSAKYGBgCgpPbiBwZXV0IGN1c3RvbWlzZXIgZW5jb3JlIHBsdXMgbGEgZMOpY29yYXRpb24gZW4gaW50ZXJ2ZW5hbnQgcGx1cyBsb3VyZGVtZW50IHN1ciBsYSBtaXNlIGVuIHBhZ2UuIFVuZSBtYW5pw6hyZSBkZSBmYWlyZSB2YSDDqnRyZSBkZSBjcsOpZXIgZGVzIHZlY3RldXJzIMOgIHBhcnRpciBkZXMgZG9ubsOpZXMsIGVuIHN1YnN0aXR1YW50IGxhIHZhbGV1ciBxdWkgbm91cyBpbnTDqXJlc3NlIHBhciBsYSBmb3JtZSBxdWUgbCdvbiBzb3VoYWl0ZSBsdWkgZG9ubmVyLiBQYXIgZXhlbXBsZSwgc2kgamUgdmV1eCBjaGFuZ2VyIGxhIGNvdWxldXIgZHUgbsWTdWQgZW4gZm9uY3Rpb24gZHUgbGFiZWwKCmBgYHtyLHJlc3VsdHM9J2hvbGQnfQojSidhaSB1bmUgY29sb25uZSBkZSBtb24gb2JqZXQgaWdyYXBoIGF2ZWMgbGVzIGxhYmVscwpWKGRhdGEpJHR5cGUKI2plIGNvcGllIGxlIGNvbnRlbnUgZGUgY2V0dGUgY29sb25uZSBkYW5zIHVuIG5vdXZlbCBvYmpldAp0b19jb2xvcnM8LVYoZGF0YSkkdHlwZQojSmUgc3Vic3RpdHVlIHRvdXRlIGxlcyBjZWxsdWxlcyBhdmVjIGwnaW5mb3JtYXRpb24gYGxpYnJhaXJlYCBwYXIgbGEgY291bGV1ciBzb3VoYWl0w6llCnRvX2NvbG9yczwtcmVwbGFjZSh0b19jb2xvcnMsdG9fY29sb3JzPT0iTGlicmFpcmUiLCJvcmFuZ2UiKQp0b19jb2xvcnMKI0plIGNvbnRpbnVlIGF2ZWMgbGVzIGF1dHJlcyB2YWxldXJzCnRvX2NvbG9yczwtcmVwbGFjZSh0b19jb2xvcnMsdG9fY29sb3JzPT0iQXV0ZXVyIiwiZ3JlZW4iKQp0b19jb2xvcnM8LXJlcGxhY2UodG9fY29sb3JzLHRvX2NvbG9ycz09IkltcHJpbWV1ciIsInJlZCIpCiNKJ29idGllbnMgdW4gbm91dmVsIG9iamV0IGF2ZWMgZGVzIGNvdWxldXJzIMOgIGxhIHBsYWNlIGRlcyBsYWJlbHMKdG9fY29sb3JzCmBgYAoKSmUgcGV1eCBkw6lzb3JtYWlzIGFwcGxpcXVlciBjZXR0ZSBjb3VsZXVyIMOgIGNoYXF1ZSBuxZN1ZAoKYGBge3J9CiNKJ2FpIHVuZSBjb2xvbm5lIGNvdWxldXIgcXVpIGVzdCB2aWRlLCBxdWUgamUgdmFpcyByZW1wbGlyIGF2ZWMgbCdvYmpldCBgdG9fY29sb3JzYCBxdWUgamUgdmllbnMgZGUgY3LDqWVyClYoZGF0YSkkY29sb3IKI0plIHJlbXBsYWNlIGxhIGNvdWxldXIgZHUgZ3JhcGhlIGF2ZWMgY2VsbGUgcXVlIGplIHZpZW5zIGRlIGTDqWZpbmlyClYoZGF0YSkkY29sb3IgPC0gdG9fY29sb3JzCiNMZSBncmFwaGUgY2hhbmdlIGRlIGNvdWxldXIKcGxvdChkYXRhKQpgYGAKCkplIHBldXggZmFpcmUgbGEgbcOqbWUgb3DDqXJhdGlvbiBhdmVjIGxhIGZvcm1lIGRlcyBuxZN1ZHMsIGV0IGFtw6lsaW9yZXIgZW5jb3JlIGxlIHJlbmR1LgoKKipBVFRFTlRJT04qKjogbGUgcmVuZHUgZGFucyBSU3R1ZGlvIG4nZXN0IHBhcyBmb3Jjw6ltZW50IG9wdGltdW06IHBlbnNleiBsJ291dnJpciBkYW5zIHVuZSBub3V2ZWxsZSBmZW7DqnRyZSBwb3VyIHZvaXIgbGUgcsOpc3VsdGF0LgoKYGBge3J9CiNPbiBjaGFuZ2UgbGEgZm9ybWUgZHUgbsWTdWQgZW4gZm9uY3Rpb24gZHUgbGFiZWwKdG9fc2hhcGU8LVYoZGF0YSkkdHlwZQp0b19zaGFwZTwtcmVwbGFjZSh0b19zaGFwZSx0b19zaGFwZT09IkF1dGV1ciIsInNxdWFyZSIpCnRvX3NoYXBlPC1yZXBsYWNlKHRvX3NoYXBlLHRvX3NoYXBlPT0iSW1wcmltZXVyIiwiY2lyY2xlIikKdG9fc2hhcGU8LXJlcGxhY2UodG9fc2hhcGUsdG9fc2hhcGU9PSJMaWJyYWlyZSIsInNwaGVyZSIpCgojSmUgcGV1eCDDoCBub3V2ZWF1IGNoYW5nZXIgbCdvYmpldCBpZ3JhcGgKVihkYXRhKSRjb2xvciA8LSB0b19jb2xvcnMKVihkYXRhKSRsYWJlbC5jb2xvciA8LSAiYmxhY2siCiNFKGRhdGEpJGVkZ2UuY29sb3IgPC0gImdyYXk4MCIKCiNvdSBiaWVuIGludGVydmVuaXIgZGlyZWN0ZW1lbnQgZGFucyBsZXMgcGFyYW3DqHRyZXMgZHUgZ3JhcGhlCnBsb3QoZGF0YSwKICAgICB2ZXJ0ZXgubGFiZWwuZGVncmVlPTIsCiAgICAgI29uIGluamVjdGUgbGUgdmVjdGV1ciBhdmVjIGxlcyBmb3JtZXMgcXVlIG5vdXMgdmVub25zIGRlIGNyw6llcgogICAgIHZlcnRleC5zaGFwZT10b19zaGFwZSwKICAgICAjdGFpbGxlIGRlcyBuxZN1ZHMKICAgICB2ZXJ0ZXguc2l6ZSA9IDEwLAogICAgICN0YWlsbGUgZGUgbGEgcG9saWNlCiAgICAgdmVydGV4LmxhYmVsLmNleD0wLjcKICAgICApIAoKdGl0bGUoIm1vbiBncmFwaGUiLCBzdWI9InByZW1pZXIgdGVzdCIpCgojSidham91dGUgdW5lIHBldGl0ZSBsw6lnZW5kZQpsZWdlbmQoeD0tMS41LCB5PS0xLjEsIGMoIkF1dGV1ciIsIkxpYnJhaXJlIiwgIkltcHJpbWV1ciIpLCBwY2g9MjEsCiAgICAgICBjb2w9IiM3Nzc3NzciLCBwdC5iZz1jKCJncmVlbiIsICJvcmFuZ2UiLCAicmVkIiksIHB0LmNleD0yLCBjZXg9LjgsIGJ0eT0ibiIsIG5jb2w9MSkKYGBgCgpOb3VzIGF2b25zIGVuY29yZSB1biBwcm9ibMOobWU6IGxlcyByZWxhdGlvbnMgbXVsdGlwbGVzIHNvbnQgdG91dGVzIGRlc3NpbsOpZXMsIGNhciBlbGxlcyBzb250IHJlc3TDqWVzIGRhbnMgbGUgdGFibGVhdS4gUXVlbGxlcyBzb250LWVsbGVzPwoKRGV1eCBwcm9ibMOobWVzIHNvbnQgcG9zc2libGVzOgoqIFVuZSBib3VjbGUgKF9sb29wXykgZXN0IHVuIG7Fk3VkIHJlbGnDqSBwYXIgdW5lIGFyw6p0ZSDDoCBsdWktbcOqbWUKKiBVbiBtdWx0aXBsZSAoX211bHRpcGxlXykgc29udCBkZXV4IG7Fk3VkcyByZWxpw6lzIHBsdXNpZXVycyBmb2lzIGVuc2VtYmxlLiBfTi5CLl8gc2kgbGUgZ3JhcGggZXN0IGRpcmlnw6kgYDItPjFgIG4nZXN0IHBhcyB1biBtdWx0aXBsZSBkZSBgMS0+MmAsIG1haXMgcydpbCBlc3QgZGlyaWfDqSBvdWkuCgpgYGB7cixyZXN1bHRzPSdob2xkJ30Kd2hpY2hfbG9vcChkYXRhKQp3aGljaF9tdWx0aXBsZShkYXRhKQpgYGAKCkNvbW1lIGonYWkgZGUgbm9tYnJldXggbXVsdGlwbGVzLCBqZSB2YWlzIGxlcyB0cmFuc2Zvcm1lciBlbiBwb2lkcyBwb3VyIGNoYXF1ZSBhcsOqdGUKCmBgYHtyLHJlc3VsdHM9J2hvbGQnfQojSmUgY29tcHRlIGxlcyBtdWx0aXBsZXMgcG91ciBjaGFxdWUgYXLDqnRlCmNvdW50X211bHRpcGxlKGRhdGEpCiNKZSBmYWlzIHVuZSBjb3BpZSBwb3VyIHRyYXZhaWxsZXIgZGVzc3VzIChzaSBqJ2FpIGJlc29pbiBkZXMgZG9ubsOpZXMgb3JpZ2luYWxlcyBwbHVzIHRhcmQpCmRhdGFfc2ltcGxpZmllZCA8LSBkYXRhCiNKZSBjb3BpZS1jb2xsZSBsZSBub21icmUgZGUgbXVsdGlwbGUgcGFyIGFyw6p0ZSBkYW5zIGxhIGNvbG9ubmUgZGVzIHBvaWRzCkUoZGF0YV9zaW1wbGlmaWVkKSR3ZWlnaHQgPC0gY291bnRfbXVsdGlwbGUoZGF0YV9zaW1wbGlmaWVkKQojamUgcmV0aXJlIGxlcyBkb3VibG9ucyAobGVzIG11bHRpcGxlcykgYXZlYyBsYSBmb25jdGlvbiBzaW1wbGlmeSgpCmRhdGFfc2ltcGxpZmllZCA8LSBzaW1wbGlmeShkYXRhX3NpbXBsaWZpZWQpCmBgYAoKSidhZmZpY2hlIG1vbiBub3V2ZWF1IGdyYXBoOiBsYSBsYXJnZXVyIGRlIGwnYXLDqnRlIGTDqXBlbmQgZMOpc29ybWFpcyBkdSBwb2lkcwoKYGBge3J9CkUoZGF0YV9zaW1wbGlmaWVkKSR3aWR0aCA8LUUoZGF0YV9zaW1wbGlmaWVkKSR3ZWlnaHQvMgpwbG90KGRhdGFfc2ltcGxpZmllZCwKICAgICAjcGFzIGRlIGNvdXJidXJlIGRlIGwnYXLDqnRlCiAgICAgZWRnZS5jdXJ2ZWQ9MCwKICAgICAjZGlzdGFuY2UgZW50cmUgbGUgbGFiZWwgZXQgbGUgbsWTdWQKICAgICB2ZXJ0ZXgubGFiZWwuZGlzdD0xLAogICAgICNDaG9peCBkZSBsYSBwb2xpY2UKICAgICB2ZXJ0ZXgubGFiZWwuZmFtaWx5PSJUaW1lcyIsCiAgICAgI0Nob2l4IGRlIGxhIGZvcm1lCiAgICAgdmVydGV4LnNoYXBlPXRvX3NoYXBlLAogICAgICMgVGFpbGUgZHUgbsWTdWQKICAgICB2ZXJ0ZXguc2l6ZSA9IDYsCiAgICAgI3RhaWxsZSBkZSBsYSBwb2xpY2UKICAgICB2ZXJ0ZXgubGFiZWwuY2V4PTAuNgogICAgICkKdGl0bGUoIkV0IHZvaWzDoCEiKQojSidham91dGUgdW5lIHBldGl0ZSBsw6lnZW5kZQpsZWdlbmQoeD0tMiwgeT0tMC41LCBjKCJBdXRldXIiLCJMaWJyYWlyZSIsICJJbXByaW1ldXIiKSwgcGNoPTIxLAogICAgICAgY29sPSIjNzc3Nzc3IiwgcHQuYmc9YygiZ3JlZW4iLCAib3JhbmdlIiwgInJlZCIpLCBwdC5jZXg9MSwgY2V4PS44LCBidHk9Im4iLCBuY29sPTEpCmBgYAoKIyBUcmFjw6kgZGUgZ3JhcGhlCgpSZXBhcnRvbnMgZGUgemVybwoKSWwgZXhpc3RlIGRpZmbDqXJlbnRlcyB2aXN1YWxpc2F0aW9uLCBhbGdvcml0aG1lcywgZXRjLiBMYSBsb2dpcXVlIGVzdCB0b3Vqb3VycyBsYSBtw6ptZTogamUgcHLDqS10cmFpdGUgbW9uIG9iamV0IGBpZ3JhcGhgIGF2ZWMgdW5lIGZvbmN0aW9uIHNww6ljaWZpcXVlIGF1IHRyYWPDqSBjaG9pc2ksIGV0IGondXRpbGlzZSBsZSByw6lzdWx0YXQgZGUgY2UgcHLDqXRyYWl0ZW1lbnQgY29tbWUgdmFsZXVyIGR1IHBhcmFtw6h0cmUgYGxheW91dGAuIEljaSwgbGUgX2NpcmN1bGFyIGxheW91dF86CgpgYGB7cn0KdG9fY2lyY2xlPC1sYXlvdXRfaW5fY2lyY2xlKGRhdGEpCnBsb3QoZGF0YSwgbGF5b3V0PXRvX2NpcmNsZSwgdmVydGV4LnNpemU9MSkKYGBgCgpJbCBleGlzdGUgdW5lIG11bHRpdHVkZSBkZSBfbGF5b3V0c18uIEplIHBldXggdG91cyBsZXMgYWZmaWNoZXIgZCd1biBjb3VwLCBwb3VyIGpldGVyIHVuIGNvdXAgZCfFk2lsIMOgIGxhIGZvcm1lIHF1J2lscyBwcmVubmVudCwgZXQgY2hvaXNpciBjZWx1aSBxdWkgbSdpbnTDqXJlc3NlIGxlIHBsdXMKCmBgYHtyLCBmaWcud2lkdGg9MTUsIGZpZy5oZWlnaHQ9NywgZHBpPTI1fQpsYXlvdXRzIDwtIGdyZXAoIl5sYXlvdXRfIiwgbHMoInBhY2thZ2U6aWdyYXBoIiksIHZhbHVlPVRSVUUpWy0xXSAKIyBKJ2VuIHJldGlyZSBjZXJ0YWlucyBzaSBqZSB2ZXV4CmxheW91dHMgPC0gbGF5b3V0c1shZ3JlcGwoImJpcGFydGl0ZXxtZXJnZXxub3JtfHN1Z2l5YW1hfHRyZWUiLCBsYXlvdXRzKV0KI2plIHByw6lwYXJlIGxhIG1pc2UgZW4gcGFnZSBkdSByw6lzdWx0YXQKcGFyKG1mcm93PWMoMywzKSwgbWFyPWMoMSwxLDEsMSkpCiNKZSBmYWlzIHVuIGJvdWNsZTogdW4gZ3JhcGggcGFyIGl0w6lyYXRpb24KZm9yIChsYXlvdXQgaW4gbGF5b3V0cykgewogIHByaW50KGxheW91dCkKICBsIDwtIGRvLmNhbGwobGF5b3V0LCBsaXN0KGRhdGEpKSAKICBwbG90KGRhdGFfc2ltcGxpZmllZCwgZWRnZS5hcnJvdy5tb2RlPTAsIGxheW91dD1sLCBtYWluPWxheW91dCkgfQpgYGAKClMnaWwgeSBlbiBhIHVuIHF1aSBtJ2ludMOpcmVzc2UsIGplIHBldXggbCdhcHBsaXF1ZXIgZGUgbGEgbcOqbWUgbWFuacOocmUgcXVlIHBvdXIgbGUgY2VyY2xlLiAKCkV2aWRlbW1lbnQsIGplIG5lIGRvaXMgY2hvaXNpciB1biBncmFwaGUgYWRhcHTDqeKApgoKYGBge3J9CmRhdGEoIktvZW5pZ3NiZXJnIikKcGxvdChLb2VuaWdzYmVyZykKYGBgCgpJbCBzZW1ibGUgcXVlIGxhIGZvcm1lIGVuIMOpdG9pbGUgc29pdCBiaWVuIGFkYXB0w6llLCDDqXRhbnQgZG9ubsOpIGxhIGNlbnRyYWxpdMOpIGRlIE1vbGnDqHJlOgoKYGBge3J9CnRvX3N0YXI8LWxheW91dF9hc19zdGFyKGRhdGEpCnBsb3QoZGF0YSwgbGF5b3V0PXRvX3N0YXIsIHZlcnRleC5zaXplPTAuMSkKYGBgCgojIyBMZXMgYWxnb3JpdGhtZXMgX2ZvcmNlZCBiYXNlXwoKTGVzIHRyYWPDqXMgbGVzIHBsdXMgaW1wb3J0YW50cyBzb250IGxlcyBfZm9yY2VkIGJhc2VfLCBxdWkgbsOpY2Vzc2l0ZW50IGRlcyBhbGdvcml0aG1lcyBwYXJ0aWN1bGllcnMuIFJlZ3Jkb25zLWxlcyBlbiBkw6l0YWlsLgoKIyMjIF9GcnVjaHRlcm1hbiBSZWluZ29sZF8KCkZydWNodGVybWFuLCBUaG9tYXMgTS4gSi47IFJlaW5nb2xkLCBFZHdhcmQgTS4gKDE5OTEpLCAiR3JhcGggRHJhd2luZyBieSBGb3JjZS1EaXJlY3RlZCBQbGFjZW1lbnQiLCBfU29mdHdhcmUg4oCTIFByYWN0aWNlICYgRXhwZXJpZW5jZV8sIFdpbGV5LCAyMSAoMTEpOiAxMTI54oCTMTE2NCwgW2RvaToxMC4xMDAyL3NwZS40MzgwMjExMTAyXShodHRwczovL2RvaS5vcmcvMTAuMTAwMi9zcGUuNDM4MDIxMTEwMikuCgpQbHVzIGQnaW5mb3JtYXRpb25zIFtpY2ldKGh0dHBzOi8vZ2l0aHViLmNvbS9nZXBoaS9nZXBoaS93aWtpL0ZydWNodGVybWFuLVJlaW5nb2xkKQoKTGUgYWxnb3JpdGhtZSBlc3QgYXNzZXogY29tcHBsaXF1w6ksIGV0IGxlIHRlbXBycyBkZSBjYWxjdWwgY29uc8OpcXVlbnQuIE9uIGwndXRpbGlzZSBwZXUgYXZlYyBkZXMgZ3JhbmRlcyBiYXNlcyBkZSBkb25uw6llcyAocGx1cyBkZSAxMCAwMDAgbsWTdWRzKS4KCmBgYHtyfQpsYXlvdXRfZnI8LWxheW91dF93aXRoX2ZyKGRhdGFfc2ltcGxpZmllZCkKRShkYXRhX3NpbXBsaWZpZWQpJHdpZHRoIDwtRShkYXRhX3NpbXBsaWZpZWQpJHdlaWdodApwbG90KGRhdGFfc2ltcGxpZmllZCwgbGF5b3V0PWxheW91dF9mciwKICAgICAjSidham91dGUgbGVzIHBvaWRzCiAgICAgd2VpZ2h0PVRSVUUsCiAgICAgI3BhcyBkZSBjb3VyYnVyZSBkZSBsJ2Fyw6p0ZQogICAgIGVkZ2UuY3VydmVkPTApCmBgYAoKT24gcGV1dCBqb3VlciBzdXIgbGVzIHBhcmFtw6h0cmVzIGV0IGF1Z21lbnRlciBsZSBub21icmUgZCdpdMOpcmF0aW9uCgpgYGB7ciwgZmlnLndpZHRoPTE1LCBmaWcuaGVpZ2h0PTcsIGRwaT0xNX0KI0plIHBhc3NlIHN1ciAyIGNvbG9ubmVzLCAyIHJhbmdzCnBhcihtZnJvdz1jKDIsIDIpKQojSidhanVzdGUgbGEgbWFyZ2UgcG91ciBsZSB0aXRyZQpwYXIob21hPWMoMSwxLDEsMSkpCgojIyBsYXlvdXRfd2l0aF9mcgpwbG90LmlncmFwaChkYXRhX3NpbXBsaWZpZWQsIGxheW91dCA9IGxheW91dF93aXRoX2ZyKGRhdGFfc2ltcGxpZmllZCwgbml0ZXIgPSAxKSwgbWFpbiA9IDEpCnBsb3QuaWdyYXBoKGRhdGFfc2ltcGxpZmllZCwgbGF5b3V0ID0gbGF5b3V0X3dpdGhfZnIoZGF0YV9zaW1wbGlmaWVkLCBuaXRlciA9IDUpLCBtYWluID0gNSkKcGxvdC5pZ3JhcGgoZGF0YV9zaW1wbGlmaWVkLCBsYXlvdXQgPSBsYXlvdXRfd2l0aF9mcihkYXRhX3NpbXBsaWZpZWQsIG5pdGVyID0gMTApLCBtYWluID0gMTApCnBsb3QuaWdyYXBoKGRhdGFfc2ltcGxpZmllZCwgbGF5b3V0ID0gbGF5b3V0X3dpdGhfZnIoZGF0YV9zaW1wbGlmaWVkLCBuaXRlciA9IDIwKSwgbWFpbiA9IDIwKQpwbG90LmlncmFwaChkYXRhX3NpbXBsaWZpZWQsIGxheW91dCA9IGxheW91dF93aXRoX2ZyKGRhdGFfc2ltcGxpZmllZCwgbml0ZXIgPSA1MCksIG1haW4gPSA1MCkKcGxvdC5pZ3JhcGgoZGF0YV9zaW1wbGlmaWVkLCBsYXlvdXQgPSBsYXlvdXRfd2l0aF9mcihkYXRhX3NpbXBsaWZpZWQsIG5pdGVyID0gNzUpLCBtYWluID0gNzUpCnBsb3QuaWdyYXBoKGRhdGFfc2ltcGxpZmllZCwgbGF5b3V0ID0gbGF5b3V0X3dpdGhfZnIoZGF0YV9zaW1wbGlmaWVkLCBuaXRlciA9IDEwMCksIG1haW4gPSAxMDApCnBsb3QuaWdyYXBoKGRhdGFfc2ltcGxpZmllZCwgbGF5b3V0ID0gbGF5b3V0X3dpdGhfZnIoZGF0YV9zaW1wbGlmaWVkLCBuaXRlciA9IDE1MCksIG1haW4gPSAxNTApCnBsb3QuaWdyYXBoKGRhdGFfc2ltcGxpZmllZCwgbGF5b3V0ID0gbGF5b3V0X3dpdGhfZnIoZGF0YV9zaW1wbGlmaWVkLCBuaXRlciA9IDIwMCksIG1haW4gPSAyMDApCnBsb3QuaWdyYXBoKGRhdGFfc2ltcGxpZmllZCwgbGF5b3V0ID0gbGF5b3V0X3dpdGhfZnIoZGF0YV9zaW1wbGlmaWVkLCBuaXRlciA9IDMwMCksIG1haW4gPSAzMDApCnBsb3QuaWdyYXBoKGRhdGFfc2ltcGxpZmllZCwgbGF5b3V0ID0gbGF5b3V0X3dpdGhfZnIoZGF0YV9zaW1wbGlmaWVkLCBuaXRlciA9IDUwMCksIG1haW4gPSA1MDApCnBsb3QuaWdyYXBoKGRhdGFfc2ltcGxpZmllZCwgbGF5b3V0ID0gbGF5b3V0X3dpdGhfZnIoZGF0YV9zaW1wbGlmaWVkLCBuaXRlciA9IDcwMCksIG1haW4gPSA3MDApCnRpdGxlKCJOby4gb2YgSXRlcmF0aW9ucyAobGF5b3V0X3dpdGhfZnIpIiwgb3V0ZXIgPSBUUlVFKQpwYXIobWZyb3c9YygxLCAxKSkKcGFyKG9tYT1jKDAsMCwwLDApKQoKYGBgCgpWb3lvbnMgbGUgcsOpc3VsdGF0IGFww6hycyA3MDAgaXTDqXJhdGlvbnM6CgpgYGB7ciwgZmlnLndpZHRoPTEwLCBmaWcuaGVpZ2h0PTYsIGRwaT0xNX0KIyMgSifDqXBhaXNzaXMgbCdhcsOqdGUgZW4gZm9uY3Rpb24gZHUgcG9pZHMKRShkYXRhX3NpbXBsaWZpZWQpJHdpZHRoIDwtRShkYXRhX3NpbXBsaWZpZWQpJHdlaWdodApwbG90LmlncmFwaChkYXRhX3NpbXBsaWZpZWQsCiAgICAgICAgICAgIGxheW91dCA9IGxheW91dF93aXRoX2ZyKGRhdGFfc2ltcGxpZmllZCwgbml0ZXIgPSA3MDApLAogICAgICAgICAgICBtYWluID0gNzAwLAogICAgICAgICAgICAjcGFzIGRlIGNvdXJidXJlIGRlIGwnYXLDqnRlCiAgICAgICAgICAgIGVkZ2UuY3VydmVkPTAsCiAgICAgICAgICAgICN0YWlsbGUgZGUgbGEgcG9saWNlCiAgICAgICAgICAgIHZlcnRleC5sYWJlbC5jZXg9MC42LAogICAgICAgICAgICAjIFRhaWxlIGR1IG7Fk3VkCiAgICAgICAgICAgIHZlcnRleC5zaXplID0gOCkKdGl0bGUoIjcwMCBpdMOpcmF0aW9ucyIsIG91dGVyID0gVFJVRSkKYGBgCgojIyMgX0RyTF8KCkxlIG5vbSBhIGNoYW5nw6kgcGx1c2lldXJzIGZvaXM6IGQnYWJvcmQgcmViYXB0aXPDqSBfdnhPcmRfLCBvbiBwYXJsZSBkJ19PcGVuT3JkXy4KCiogTWFydGluLCBTLiwgQnJvd24sIFcuTS4sIEtsYXZhbnMsIFIuLCBCb3lhY2ssIEsuVy4sIERyTDogRGlzdHJpYnV0ZWQgUmVjdXJzaXZlIChHcmFwaCkgTGF5b3V0LiBTQU5EIFJlcG9ydHMsIDIwMDguIDI5MzY6IHAuIDEtMTAuCiogUy4gTWFydGluLCBXLiBNLiBCcm93biwgUi4gS2xhdmFucywgYW5kIEsuIEJveWFjayAodG8gYXBwZWFyLCAyMDExKSwgIk9wZW5PcmQ6IEFuIE9wZW4tU291cmNlIFRvb2xib3ggZm9yIExhcmdlIEdyYXBoIExheW91dCwiIFNQSUUgQ29uZmVyZW5jZSBvbiBWaXN1YWxpemF0aW9uIGFuZCBEYXRhIEFuYWx5c2lzIChWREEpLgoKUGx1cyBkJ2luZm9ybWF0aW9ucyBbaWNpXShodHRwczovL2dpdGh1Yi5jb20vZ2VwaGkvZ2VwaGkvd2lraS9PcGVuT3JkKQoKSWwgdmEgdGVudGVyIGRlIGZhaXJlIHJlc3NvcnRpciBhdSBtYXhpbXVtIGRlcyBncmFuZHMgY2x1c3RlcnMgdHLDqHMgbmV0cyBlbiBjb3VwYW50IGxlcyBsaWVucyBsZXMgcGx1cyBsb25ncy4gRXZpZGVtbWVudCBjZXQgYWxnb3JpdGhtZSBuw6ljZXNzaXRlIGRlcyBncmFwaGVzIGRlIGdyYW5kZSB0YWlsbGUsIG5vdXMgY2hhcmdlb25zIGRvbmMgdW4gZ3JvcyBqZXUgZGUgZG9ubsOpZXMgdGlyw6kgZHUgcGFja2FnZSBgaWdyYXBoZGF0YWAuCgpgYGB7cn0KZGF0YSgiVVNhaXJwb3J0cyIpCiNPbiB0cmFjZSBsZSBncmFwaGUKbGF5b3V0X2RybCA8LSBsYXlvdXQuZHJsKFVTYWlycG9ydHMpCnBsb3QoVVNhaXJwb3J0cywgbGF5b3V0PWxheW91dF9kcmwsIG1haW49IkRyTCIpCmBgYAoKTm91cyBwb3V2b25zIGNvbXBhcmVyIGwnZWZmZXQgZGUgY2UgZMOpY291cGFnZSBhdmVjIGNlbHVpIGVmZmVjdHXDqSBwYXIgbCdhbGdvcml0aG1lIHByw6ljw6lkZW50LCBfRnJ1Y2h0ZXJtYW4gUmVpbmdvbGRfCgpgYGB7ciwgZmlnLndpZHRoPTE1LCBmaWcuaGVpZ2h0PTcsIGRwaT0yNX0KcGFyKG1mcm93PWMoMSwgMikpCnBhcihvbWE9YygwLDAsMiwwKSkKcGxvdChVU2FpcnBvcnRzLCBsYXlvdXQ9bGF5b3V0X3dpdGhfZnIoVVNhaXJwb3J0cyksIHdlaWdodD1ULCBtYWluPSJGUiIpCnBsb3QoVVNhaXJwb3J0cywgbGF5b3V0PWxheW91dF9kcmwsIG1haW49IkRyTCIpCmBgYAoKIyMgbGUgYEdlb2xheW91dGAKCkonYWkgcHLDqXBhcsOpIHVuIHRvdXQgcGV0aXQgamV1IGRlIGRvbm7DqWVzIGF2ZWMgZGVzIGNvb3Jkb25uw6llcyBnw6lvZ3JhcGhpcXVlcwoKYGBge3IscmVzdWx0cz0naG9sZCd9Cm5vZGVzX2dlbyA8LSBhcy5kYXRhLmZyYW1lKHJlYWQuY3N2KGZpbGU9ImRhdGEvZ2VvL25vZGVzLmNzdiIsIHNlcCA9ICJcdCIsIGhlYWRlciA9IEZBTFNFKSkKZWRnZXNfZ2VvIDwtIGFzLmRhdGEuZnJhbWUocmVhZC5jc3YoZmlsZT0iZGF0YS9nZW8vZWRnZXMuY3N2Iiwgc2VwID0gIlx0IiwgaGVhZGVyID0gRkFMU0UpKQojSmUgZG9ubmUgdW4gbm9tIGF1eCBjb2xvbm5lcyBkZSBjaGFxdWUgZGF0YS5mcmFtZQpjb2xuYW1lcyhub2Rlc19nZW8pIDwtIGMoImlkIiwgImxhYmVsIiwibGF0IiwibG9uZyIpCmNvbG5hbWVzKGVkZ2VzX2dlbykgPC0gYygiZnJvbSIsICJ0byIpCm5vZGVzX2dlbwplZGdlc19nZW8KYGBgCgpKZSB0cmFuc2Zvcm1lIGNlcyBkZXV4IG9iamV0cyBlbiBkb25uw6llcyBgaWdyYXBoYCwgcXVpIHZvbnQgbWUgcGVybWV0dHJlIGRlIGZhaXJlIG1lcyBhbmFseXNlcyBkZSByw6lzZWF1IHBhciBsYSBzdWl0ZS4KCmBgYHtyfQpkYXRhX2dlbyA8LSBncmFwaF9mcm9tX2RhdGFfZnJhbWUoZD1lZGdlc19nZW8sIHZlcnRpY2VzPW5vZGVzX2dlbywgZGlyZWN0ZWQ9RikgCmNsYXNzKGRhdGFfZ2VvKQpwbG90KGRhdGFfZ2VvKQpgYGAKCkplIHByb2pldHRlIGNlIHLDqXNlYXUgc3VyIHVuZSBjYXJ0ZSwgZW4gcGxhw6dhbnQgbGVzIG7Fk3VkcyBlbiBmb25jdGlvbiBkZSBsZXVycyBjb29yZG9ubsOpZXMgZ8Opb2dyYXBoaXF1ZXMKCmBgYHtyfQojSmUgZMOpZmluaXMgbGVzIGxhdCBldCBsb25nIGRlIG1vbiBjYWRyZQp3ZXN0ZXJuX2V1cm9wZTwtYyhsZWZ0ID0gLTEyLCBib3R0b20gPSA0MCwgcmlnaHQgPSAyMCwgdG9wID0gNTUpCiNKZSByw6ljdXDDqHJlIG1vbiBmb25kIGRlIGNhcnRlIHNlbG9uIGxlcyBkaW1lbnNpb25zIHByw6l2dWVzIHN1cHJhCm1hcCA8LSBnZXRfc3RhbWVubWFwKHdlc3Rlcm5fZXVyb3BlLCB6b29tPTYsIHNvdXJjZT0ic3RhbWVuIiwgbWFwdHlwZT0idG9uZXItbGl0ZSIsIGZpbGV0eXBlPSJwbmciKQojSmUgY3LDqWUgdW5lIGNhcnRlIMOgIHBhcnRpciBkZSBtb24gZm9uZCBkZSBjYXJ0ZQpwPC1nZ21hcChtYXApCiNKJ2Fqb3V0ZSBsZXMgYXLDqnRlcwpwID0gcCArIGdlb21fZWRnZXNldChhZXMoeD1sb25nLCB5PWxhdCksIGRhdGFfZ2VvLCBjb2xvdXI9Z3JheSgwLjEsIDAuMyksIHNpemU9MSkKI0onYWpvdXRlIGxlcyBuxZN1ZHMKcCA9IHAgKyBnZW9tX25vZGVzZXQoYWVzKHg9bG9uZywgeT1sYXQpLCBkYXRhX2dlbywgc2l6ZT0zLCBjb2xvdXI9InJlZCIpCiNKJ2FmZmljaGUgbGUgdG91dApwCmBgYAoKIyBMYSBmb3JjZSBkZXMgbGllbnMKCiMjIExlcyBtZXN1cmVzCgpEZW5zaXTDqSAoX2RlbnNpdHlfKTogbGEgcHJvcG9ydGlvbiBkZSBsaWVucyBkYW5zIHVuIHLDqXNlYXUgcmVsYXRpdmVtZW50IGF1IHRvdGFsIGRlcyBsaWVucyBwb3NzaWJsZXMuCgpgYGB7cixyZXN1bHRzPSdob2xkJ30KZWRnZV9kZW5zaXR5KGRhdGEpCmBgYAoKQ2VudHJhbGl0w6kgZGUgcHJveGltaXTDqTogRGlzdGFuY2UgbW95ZW5uZSBkdSBuxZN1ZCDDoCB0b3VzIGxlcyBhdXRyZXMgbsWTdWRzIChfQ2xvc2VuZXNzXykKCmBgYHtyLHJlc3VsdHM9J2hvbGQnfQpjbG9zZW5lc3MuY2VudCA8LSBjbG9zZW5lc3MoZGF0YSkKY2xvc2VuZXNzLmNlbnQKYGBgCgpQb3VyIHJhcHBlbCwgbGVzIG5vbXMgYXR0YWNow6lzIHNvbnQgYWNjZXNzaWJsZXMgYWluc2k6CgpgYGB7cixyZXN1bHRzPSdob2xkJ30KY2JpbmQoVihkYXRhKSRsYWJlbCxjbG9zZW5lc3MuY2VudCkKYGBgCgpDZW50cmFsaXTDqSBk4oCZaW50ZXJtw6lkaWFyaXTDqTogTm9tYnJlIGRlIGZvaXMgcXVlIGxlIG7Fk3VkIHNlIHRyb3V2ZSBzdXIgbGUgcGx1cyBjb3VydCBjaGVtaW4gZW50cmUgZGV1eCBhdXRyZXMgbsWTdWRzIChfQmV0d2Vlbm5lc3NfKQoKYGBge3IscmVzdWx0cz0naG9sZCd9CmNsb3NlbmVzcy5iZXQgPC0gYmV0d2Vlbm5lc3MoZGF0YSkKY2xvc2VuZXNzLmJldApgYGAKCkNlbnRyYWxpdMOpIGRlIHZlY3RldXJzIHByb3ByZXM6IFNjb3JlIGTigJlhdXRvcml0w6kgYXR0cmlidcOpIMOgIHVuIG7Fk3VkIGVuIGZvbmN0aW9uIGR1IHNjb3JlIGRlIHNlcyB2b2lzaW5zLiAoX0VpZ2VudmVjdG9yXykuCgpgYGB7cixyZXN1bHRzPSdob2xkJ30KY2xvc2VuZXNzLmVpZyA8LSBlaWdlbl9jZW50cmFsaXR5KGRhdGEpCmNsb3NlbmVzcy5laWckdmVjdG9yCmBgYAoKQ2VudHJhbGl0w6kgZGUgZGVncsOpOiBOb21icmUgZGUgY29ubmV4aW9ucyBkdSBuxZN1ZCAoX0RlZ3JlZV8pCgpgYGB7cixyZXN1bHRzPSdob2xkJ30KY2xvc2VuZXNzLmRlZyA8LSBkZWdyZWUoZGF0YV9zaW1wbGlmaWVkKQpjbG9zZW5lc3MuZGVnCmBgYAoKT24gcGV1dCByw6l1dGlsaXNlciBjZXMgZG9ubsOpZXMgcG91ciBsYSB2aXN1YWxpc2F0aW9uLCBlbiBhanVzdGFudCBsYSB0YWlsbGUgZGVzIG7Fk3VkcyDDoCBsYSBjZW50cmFsaXTDqSBkZSBkZWdyw6kKCmBgYHtyLHJlc3VsdHM9J2hvbGQnfQpWKGRhdGFfc2ltcGxpZmllZCkkc2l6ZSA8LSAoY2xvc2VuZXNzLmRlZyowLjMpCnBsb3QoZGF0YV9zaW1wbGlmaWVkLCBsYXlvdXQ9bGF5b3V0X2ZyLCBtYWluPSJGUiIpCmBgYAoKT24gcGV1dCBhanVzdGVyIGNldHRlIHRhaWxsZSBhdmVjIGQnYXV0cmVzIG1lc3VyZXMgZGUgY2VudHJhbGl0w6ksIGNvbW1lIGxhIGNlbnRyYWxpdMOpIGRlIHZlY3RldXIgCgpgYGB7cixyZXN1bHRzPSdob2xkJ30KVihkYXRhX3NpbXBsaWZpZWQpJHNpemUgPC0gKGNsb3NlbmVzcy5laWckdmVjdG9yKjMwKQpwbG90KGRhdGFfc2ltcGxpZmllZCwgbGF5b3V0PWxheW91dF9mciwgbWFpbj0iRlIiKQpgYGAKCiMjIFVuIGV4ZW1wbGUgZCdhbmFseXNlIGRlIGxhIGNlbnRyYWxpdMOpCgpUZW50b25zIHVuZSBhcHByb2NoZSBwbHVzIHByYXRpcXVlIGF2ZWMgdW4gcsOpc2VhdSBjw6lsw6hicmU6IGNlbHVpIGRlIGxhIEZsb3JlbmNlIGRlIGxhIFJlbmFpc3NhbmNlIChkaXNwb25pYmxlIGRhbnMgbGUgcGFja2FnZSBgbmV0cmFua3JgKS4KCmBgYHtyLHJlc3VsdHM9J2hvbGQnfQpkYXRhKCJmbG9yZW50aW5lX20iKQojVW5lIGZhbWlsbGUgbidlc3QgcGFzIHJlbGnDqWUgYXV4IGF1dHJlczogbGEgZmFtaWxsZSBQdWNjaQpkZWdyZWUoZmxvcmVudGluZV9tKT09MAojT24gbGEgcmV0aXJlIHBvdXIgc2ltcGxpZmllciBsYSB2aXN1YWxpc2F0aW9uCmZsb3JlbmNlIDwtIGRlbGV0ZV92ZXJ0aWNlcyhmbG9yZW50aW5lX20sd2hpY2goZGVncmVlKGZsb3JlbnRpbmVfbSk9PTApKQpgYGAKCkonb2J0aWVucyB1biBqb2xpIGdyYXBoZToKCmBgYHtyfQpwbG90LmlncmFwaChmbG9yZW5jZSwgbGF5b3V0ID0gbGF5b3V0X3dpdGhfZnIoZmxvcmVuY2UsIG5pdGVyID0gNTAwKSwKICAgICAgICAgICAgICAgICAgICAgIG1haW4gPSAiRmxvcmVuY2UgYXUgWFbDqG1lIHMuIikKYGBgCgpKZSBwZXV4IHByb3BvcnRpb25uZXIgbGEgdGFpbGxlIGRlcyBuxZN1ZHMgZW4gZm9uY3Rpb24gZGUgbGEgZm9ydHVuZSBkZSBjaGFxdWUgZmFtaWxsZToKCmBgYHtyfQpwbG90KGZsb3JlbmNlLAogICAgIGxheW91dCA9IGxheW91dF93aXRoX2ZyKGZsb3JlbmNlLCBuaXRlciA9IDUwMCksCiAgICAgdmVydGV4LmxhYmVsLmNleD1WKGZsb3JlbmNlKSR3ZWFsdGgqMC4wMTIsCiAgICAgdmVydGV4LnNpemU9VihmbG9yZW5jZSkkd2VhbHRoKjAuMikKYGBgCgpNYWlzIGVzdC1jZSBxdWUgbGEgcmljaGVzc2UgZmFpdCB0b3V0PyBQcm9iYWJsZW1lbnQgcGFz4oCmIHRlbnRvbnMgZCfDqXZhbHVlciBsYSBjZW50cmFsaXTDqSBkZXMgZGlmZsOpcmVudGVzIGZhbWlsbGVzCgpgYGB7cixyZXN1bHRzPSdob2xkJ30KI0plIGZhaXMgdW4gZGF0YS1mcmFtZSDDoCBwYXJ0aXIgZGUgZGlmZsOpcmVudHMgY2FsY3VscyBkZSBjZW50cmFsaXTDqQpjZW50LmRhdGFfZnJhbWUgPC0gZGF0YS5mcmFtZSgKICBkZWdyZWUgPSBkZWdyZWUoZmxvcmVuY2UpLAogIGJldHdlZW5uZXNzID0gYmV0d2Vlbm5lc3MoZmxvcmVuY2UpLAogIGNsb3NlbmVzcyA9IGNsb3NlbmVzcyhmbG9yZW5jZSksCiAgZWlnZW52ZWN0b3IgPSBlaWdlbl9jZW50cmFsaXR5KGZsb3JlbmNlKSR2ZWN0b3IsCiAgc3ViZ3JhcGggPSBzdWJncmFwaF9jZW50cmFsaXR5KGZsb3JlbmNlKSkKI0plIHBldXggYWNjw6lkZXIgYXUgcsOpc3VsdGF0IHNvdXMgbGEgZm9ybWUgZGUgdGFibGVhdSBxdWkgcsOpc3VtZSB0b3V0ZXMgbGVzIGRvbm7DqWVzClZpZXcoY2VudC5kYXRhX2ZyYW1lKQoKIyBKZSBkb25uZSBsZSBub20gZGUgbGEgZmFtaWxsZSBsYSBwbHVzIGNlbnRyYWxlIHBvdXIgY2hhcXVlIG1lc3VyZQpWKGZsb3JlbmNlKSRuYW1lW2FwcGx5KGNlbnQuZGF0YV9mcmFtZSwyLHdoaWNoLm1heCldCmBgYAoKIyBWaXN1YWxpc2VyCgpJbCBlc3QgcG9zc2libGUgZGUgcHJvcG9zZXIgdW5lIGZvdWxlIGRlIHZpc3VhbGlzYXRpb24uIFBhciBleGVtcGxlLCBpbCBlc3QgcG9zc2libGUgZGUgcmVtcGxhY2VyIGxlcyBsYWJlbHMgcGFyIGxhIGRpc3RhbmNlIHF1aSBzw6lwYXJlIHVuIG7Fk3VkIGQndW4gYXV0cmUg4oCTIGljaSwgVGhvbWFzIEpvbGx5LgoKYGBge3J9CmRpc3QudGhvSm8gPC0gZGlzdGFuY2VzKGRhdGEsIHY9VihkYXRhKVtsYWJlbD09IlRob21hcyBKb2xseSJdLCB0bz1WKGRhdGEpLCB3ZWlnaHRzPU5BKQojIFNldCBjb2xvcnMgdG8gcGxvdCB0aGUgZGlzdGFuY2VzOgoKZ3JlZW4uZGFyayA8LSBjb2xvclJhbXBQYWxldHRlKGMoImRhcmtncmVlbiIsICJsaWdodGdyZWVuIikpCmNvbCA8LSBncmVlbi5kYXJrKG1heChkaXN0LnRob0pvKSsxKQpjb2wgPC0gY29sW2Rpc3QudGhvSm8rMV0KCnBsb3QoZGF0YSwgdmVydGV4LmNvbG9yPWNvbCwgdmVydGV4LmxhYmVsPWRpc3QudGhvSm8pCmBgYAoKT24gcGV1dCBtZXR0cmUgZW4gdmFsZXVyIGxlIGNoZW1pbiBsZSBwbHVzIGNvdXJ0IGVudHJlIGRldXggcG9pbnMKCmBgYHtyfQptb25fY2hlbWluIDwtIHNob3J0ZXN0X3BhdGhzKGRhdGEsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgZnJvbSA9IFYoZGF0YSlbbGFiZWw9PSJUaG9tYXMgSm9sbHkiXSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdG8gID0gVihkYXRhKVtsYWJlbD09IlBpZXJyZSBDb3JuZWlsbGUiXSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICNqZSBjb2xvcmllIGxlIG7Fk3VkIGV0IGwnYXLDqnRlCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgb3V0cHV0ID0gImJvdGgiKQoKIyBPbiBnw6luw6hyZSB1bmUgY291bGV1ciBwb3VyIGxlcyBhcsOqdGVzIGVuIGZvbmN0aW9uIGR1IGNoZW1pbgpjb3VsZXVyX2FyYyA8LSByZXAoImdyYXk4MCIsIGVjb3VudChkYXRhKSkKY291bGV1cl9hcmNbdW5saXN0KG1vbl9jaGVtaW4kZXBhdGgpXSA8LSAib3JhbmdlIiAKIkNvdWxldXIgZGVzIGFyY3MiCmNvdWxldXJfYXJjICNjZi4gMTI4IGV0IDIxOQoKIyBPbiBnw6luw6hyZSB1bmUgbGFyZ2V1ciBwb3VyIGwnYXLDqnRlIGVuIGZvbmN0aW9uIGR1IGNoZW1pbgpsYXJnZXVyX2FyYyA8LSByZXAoMiwgZWNvdW50KGRhdGEpKQpsYXJnZXVyX2FyY1t1bmxpc3QobW9uX2NoZW1pbiRlcGF0aCldIDwtIDYKIkxhcmdldXIgZGVzIGFyY3MiCmxhcmdldXJfYXJjICNjZi4gMTI4IGV0IDIxOQoKIyBHZW5lcmF0ZSBub2RlIGNvbG9yIHZhcmlhYmxlIHRvIHBsb3QgdGhlIHBhdGg6CmNvbGV1cl9ub2V1ZCA8LSByZXAoImdyYXk0MCIsIHZjb3VudChkYXRhKSkKY29sZXVyX25vZXVkW3VubGlzdChtb25fY2hlbWluJHZwYXRoKV0gPC0gImdvbGQiCiJMZXMgbsWTdWRzIgpjb2xldXJfbm9ldWQgI2NmLiAxIGV0IDEzCgpwbG90KGRhdGEsIHZlcnRleC5jb2xvcj1jb2xldXJfbm9ldWQsIGVkZ2UuY29sb3I9Y291bGV1cl9hcmMsIAogICAgIGVkZ2Uud2lkdGg9bGFyZ2V1cl9hcmMsIGVkZ2UuYXJyb3cubW9kZT0wKQpgYGAKCk9uIHBldXQgYXVzc2kgcmVncm91cGVyIGVuIGNsdXN0ZXIgbGVzIGRvbm7DqWVzLCBxdWUgbCdvbiByZXByw6lzZW50ZSBlbiBkZW5kb2dyYW1tZSwgY29tbWUgcG91ciBsYSBzdHlsb23DqXRyaWUKCmBgYHtyfQpjZWIgPC0gY2x1c3Rlcl9lZGdlX2JldHdlZW5uZXNzKGRhdGEpIApkZW5kUGxvdChjZWIsIG1vZGU9ImhjbHVzdCIpCmBgYAoKSmUgcHJvamV0dGUgZW5zdWl0ZSBtYSBjbGFzc2lmaWNhdGlvbiBzdXIgbW9uIGdyYXBoCgpgYGB7cn0KcGxvdChjZWIsIGRhdGEpIApgYGAKCk9uIHBldXQgbCdhZmZpY2hlciBlbiAzZC4gUG91ciBjZWxhIGondXRpbGlzZSBsZSBwYXJhbcOodHJlIGRpbT0zIHBvdXIgbW9uIGxheW91dC4KCmBgYHtyfQpjb29yZHMgPC0gbGF5b3V0X3dpdGhfZnIoZGF0YV9zaW1wbGlmaWVkLCBkaW09MykKb3BlbjNkKCkKcmdscGxvdChkYXRhLCBsYXlvdXQ9Y29vcmRzKQpgYGAKCkplIHBldXggZmFpcmUgdW5lIHNhdXZlZ2FyZGUsIG5vdGFtbWVudCBlbiBIVE1MIHBvdXIgbCdvdXZyaXIgZGFucyBsZSBuYXZpZ2F0ZXVyCgpgYGB7cn0KZGlyZm9sZGVyPWdldHdkKCkKI29wZW4zZCBwbHV0w7R0IHF1ZSByZ2wub3BlbigpIHBvdXIgdW5lIHNhdXZlZ2FyZGUKb3BlbjNkKCkKcmdscGxvdChkYXRhX3NpbXBsaWZpZWQsIGxheW91dD1jb29yZHMpCgojSmUgcHLDqXBhcmUgbCdhbmdsZQpyZ2wudmlld3BvaW50KHRoZXRhPTAsIHBoaT0wKQoKI1NhdXZlZ2FyZGVyIHVuIHNjcmVlbnNob3QgKGVuIHBuZykKcmdsLnNuYXBzaG90KHBhc3RlKGRpcmZvbGRlciwibW9uR1JhcGgzZC5wbmciLHNlcD0iIiksIGZtdD0icG5nIiwgdG9wPVRSVUUpCgojU2F1dmVnYXJkZSBlbiBodG1sCnJnbGZvbGRlcj13cml0ZVdlYkdMKGRpciA9IHBhc3RlKGRpcmZvbGRlciwiZmlyc3RfbmV0M2QiLHNlcD0iIiksIHdpZHRoPTkwMCkKCiNKJ291dnJlIGxlIHLDqXN1bHRhdCBkYW5zIGxlIG5hdmlnYXRldXIKYnJvd3NlVVJMKHJnbGZvbGRlcikKYGBgCgpKZSBwZXV4IHByb2R1aXJlIHVuZSB2aXN1YWxpc2F0aW9uIGludGVyYWN0aXZlIGRpcmVjdGVtZW50IGRhbnMgYFJgLiBKZSBwcsOpcGFyZSBsZXMgZG9ubsOpZXMKCmBgYHtyLCBpbmNsdWRlPVR9CiMgamUgY29udmVydGlzIG1vbiBpZ3JhcGhlIGVuIHVuZSBsaXN0ZSAgY29tcG9zw6llIGRlIGRldXggZGF0YS5mcmFtZXMgKG5vZGVzIGV0IGVkZ2VzKQpkYXRhXzNkX3ZpcyA8LSB0b1Zpc05ldHdvcmtEYXRhKGRhdGEpCgojIFBvdXIgbGUgbWVudSBkw6lyb3VsYW50IChjZiBpbmZyYSkKbmFtZXMgPC0gc29ydChkYXRhXzNkX3ZpcyRub2RlcyRsYWJlbCkKYGBgCgpFdCBqZSBsYW5jZSB1bmUgdmlzdWFsaXNhdGlvbiBlbiAzRAoKYGBge3IsIGluY2x1ZGU9VH0KdmlzTmV0d29yayhub2RlcyA9IGRhdGFfM2RfdmlzJG5vZGVzLAogICAgICAgICAgIGVkZ2VzID0gZGF0YV8zZF92aXMkZWRnZXMsCiAgICAgICAgICAgbWFpbiA9ICJNb24gZ3JhcGhlIGludGVyYWN0aWYiLAogICAgICAgICAgIHN1Ym1haW4gPSAiQWxvZ2lyaHRtZSBkZSBGcnVjaHRlcm1hbuKAk1JlaW5nb2xkIiwKICAgICAgICAgICBmb290ZXIgPSAiV293IikgJT4lCiAgI0plIHRyYWNlIGxlIGdyYXBoZQogIHZpc0lncmFwaExheW91dChsYXlvdXQgPSAibGF5b3V0X3dpdGhfZnIiLCAKICAgICAgICAgICAgICAgICAgc21vb3RoID0gRkFMU0UsCiAgICAgICAgICAgICAgICAgICNKJ2Fqb3V0ZSBkZSBsYSBkeW5hbWlxdWUgKGNmLiBfaW5mcmFfKQogICAgICAgICAgICAgICAgICBwaHlzaWNzID0gVFJVRQogICAgICAgICAgICAgICAgKQpgYGAKCkplIHJham91dGUgZGVzIG9wdGlvbnMgZGUgdmlzdWFsaXNhdGlvbiwgY29tbWUgdW5lIG1vZGlmaWNhdGlvbiBkZXMgbsWTdWRzIHMnaWxzIHNvbnQgc8OpbGVjdGlvbm7DqXMsIG91IHVuIHNlbGVjdGV1ciBzb3VzIGxhIGZvcm1lIGRlIGxpc3RlIGTDqXJvdWxhbnRlCgpgYGB7ciwgaW5jbHVkZT1UfQp2aXNOZXR3b3JrKG5vZGVzID0gZGF0YV8zZF92aXMkbm9kZXMsCiAgICAgICAgICAgZWRnZXMgPSBkYXRhXzNkX3ZpcyRlZGdlcywKICAgICAgICAgICBtYWluID0gIk1vbiBncmFwaGUgaW50ZXJhY3RpZiIsCiAgICAgICAgICAgc3VibWFpbiA9ICJBbG9naXJodG1lIGRlIEZydWNodGVybWFu4oCTUmVpbmdvbGQiLAogICAgICAgICAgIGZvb3RlciA9ICJXb3ciKSAlPiUKICAjSmUgdHJhY2UgbGUgZ3JhcGhlCiAgdmlzSWdyYXBoTGF5b3V0KGxheW91dCA9ICJsYXlvdXRfd2l0aF9mciIsIAogICAgICAgICAgICAgICAgICBzbW9vdGggPSBGQUxTRSwKICAgICAgICAgICAgICAgICAgI0onYWpvdXRlIGRlIGxhIGR5bmFtaXF1ZSAoY2YuIF9pbmZyYV8pCiAgICAgICAgICAgICAgICAgIHBoeXNpY3MgPSBUUlVFCiAgICAgICAgICAgICAgICApICU+JQogICNKZSBtZXRzIGVuIHZhbGV1ciBsZXMgbsWTdWRzIGxpw6lzCiAgdmlzT3B0aW9ucyhoaWdobGlnaHROZWFyZXN0ID0gbGlzdChlbmFibGVkID0gVFJVRSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICNzw6lwYXLDqXMgZGUgMSBkZWdyw6kKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRlZ3JlZSA9IDEsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjaWwgcydpbGx1bWluZW50IHF1YW5kIGxhIHNvdXJpcyBwYXNzZSBzdXIgbGUgbsWTdWQKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGhvdmVyID0gVFJVRSksCiAgICAgICAgICAgICAjSmUgY3LDqWUgdW4gc8OpbGVjdGV1cgogICAgICAgICAgICAgbm9kZXNJZFNlbGVjdGlvbiA9IGxpc3QoZW5hYmxlZCA9IFRSVUUsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB2YWx1ZXMgPSBuYW1lcykpCmBgYAoKSmUgdmFpcyBhdm9pciBiZXNvaW4gImQnw6ljYXJ0ZXIiIG1vbiBncmFwaGUsIGVuIGFqb3V0YW50IGRlIGxhIHLDqXB1bHNpb24gZW50cmUgbGVzIG7Fk3VkcyAoY2UgcXVpIG4nZXN0IHBhcyB0w6JjaGUgZmFjaWxl4oCmKQoKYGBge3IsIGluY2x1ZGU9VFJVRX0KZGF0YV8zZF92aXNfcGxvdCA8LSB2aXNOZXR3b3JrKG5vZGVzID0gZGF0YV8zZF92aXMkbm9kZXMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBlZGdlcyA9IGRhdGFfM2RfdmlzJGVkZ2VzLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWFpbiA9ICJNb24gZ3JhcGhlIGludGVyYWN0aWYiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc3VibWFpbiA9ICJBbG9naXJodG1lIGRlIEZydWNodGVybWFu4oCTUmVpbmdvbGQiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZm9vdGVyID0gIldvdyIpICU+JQogICAgICAgICAgICAgICAgICAgICNKZSB0cmFjZSBsZSBncmFwaGUKICAgICAgICAgICAgICAgICAgICB2aXNJZ3JhcGhMYXlvdXQobGF5b3V0ID0gImxheW91dF93aXRoX2ZyIiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNtb290aCA9IEZBTFNFLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjSidham91dGUgZGUgbGEgZHluYW1pcXVlIChjZi4gX2luZnJhXykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcGh5c2ljcyA9IFRSVUUKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKSAlPiUKICAgICAgICAgICAgICAgICAgICAjSmUgbWV0cyBlbiB2YWxldXIgbGVzIG7Fk3VkcyBsacOpcwogICAgICAgICAgICAgICAgICAgIHZpc09wdGlvbnMoaGlnaGxpZ2h0TmVhcmVzdCA9IGxpc3QoZW5hYmxlZCA9IFRSVUUsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICNzw6lwYXLDqXMgZGUgMSBkZWdyw6kKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZGVncmVlID0gMSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgI3Bhc3NhZ2Ugc291cmlzCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGhvdmVyID0gVFJVRSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICNKZSBjcsOpZSB1biBzw6lsZWN0ZXVyCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG5vZGVzSWRTZWxlY3Rpb24gPSBsaXN0KGVuYWJsZWQgPSBUUlVFLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB2YWx1ZXMgPSBuYW1lcykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKSAlPiUKICAgICAgICAgICAgICAgICAgICAjdGFpbGxlIGRlcyBuxZN1ZHMKICAgICAgICAgICAgICAgICAgICB2aXNOb2RlcyhzaXplID0gNTApICU+JQogICAgICAgICAgICAgICAgICAgICNjb3VsZXVyIGRlcyBhcsOqdGVzCiAgICAgICAgICAgICAgICAgICAgdmlzRWRnZXMoY29sb3IgPSBsaXN0KGhpZ2hsaWdodCA9ICJsaWdodGdyYXkiKSkgJT4lCiAgICAgICAgICAgICAgICAgICAgI0plIHBhcmFtw6h0cmUgbGEgcsOpcHVsc2lvbgogICAgICAgICAgICAgICAgICAgIHZpc1BoeXNpY3MoI1bDqWxvY2l0w6kgZGVzIG7Fk3VkcwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWF4VmVsb2NpdHkgPSAxLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgI3R5cGUgZGUgcsOpcHVsc2lvbiBoacOpcmFyY2hpcXVlCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzb2x2ZXIgPSAiZm9yY2VBdGxhczJCYXNlZCIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjcGFyYW3DqHRyZXMgZHUgZm9yY2VBdGxhczJCYXNlZAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgI2xhIGBncmF2aXRhdGlvbmFsQ29uc3RhbnRgIGTDqWNyaXQgbGEgcsOpcHVsc2lvbiAobCfDqWNhcnRlbWVudCBlbnRyZSBsZXMgbsWTdWRzKSwgbGUgY2hpZmZyZSBlc3QgZG9uYyBuw6lnYXRpZiwgc2lub24gb25jcsOpZSBkZSBsJ2F0dHJhY3Rpb24KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGZvcmNlQXRsYXMyQmFzZWQgPSBsaXN0KGdyYXZpdGF0aW9uYWxDb25zdGFudCA9IC0xMDAwKQogICAgICAgICAgICAgICAgICAgICApCgpkYXRhXzNkX3Zpc19wbG90CmBgYAoKIyBTYXV2ZWdhcmRlcwoKT24gc2F1dmVnYXJkZSBsZSByw6lzdWx0YXQKYGBge3IsIGluY2x1ZGU9VFJVRX0Kd3JpdGVfZ3JhcGgoZGF0YSwgImVkZ2VsaXN0LnR4dCIsIGZvcm1hdD0iZWRnZWxpc3QiKQpzdmcoZmlsZT0ibW9uR3JhcGguc3ZnIikKcGxvdChkYXRhKQpkZXYub2ZmKCkKCnBuZyhmaWxlPSJtb25HcmFwaC5wbmciKQpwbG90KGRhdGEpCmRldi5vZmYoKQpgYGAKCiFbMTAwJSBjZW50ZXJdKG1vbkdyYXBoLnBuZykKCiFbMTAwJSBjZW50ZXJdKG1vbkdyYXBoLnN2ZykKCgoKCgo=